Maximum Non-overlapping Flights

You are given several test cases. In each test case, you are provided with a number N representing the total number of flights. For each flight, you are given a departure time and an arrival time.

Your task is to determine the maximum number of flights that can be scheduled without overlapping. A flight can be scheduled if its departure time is not earlier than the arrival time of the previously scheduled flight.

Formal Description:

For each test case, let the flights be represented as pairs \((d, a)\) where \(d\) is the departure time and \(a\) is the arrival time. You need to select a set of flights \(S\) such that for any two consecutive flights \((d_i, a_i)\) and \((d_j, a_j)\) in \(S\), the condition \(d_j \ge a_i\) holds, and \(|S|\) is maximized.

The greedy strategy of sorting the flights by their arrival time \(a\) and then selecting non-overlapping flights works optimally.

Input Format (as described in the input section below): The first line contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(N\) representing the number of flights, followed by \(N\) lines each containing two integers that denote the departure and arrival times of each flight.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N
d1 a1
…
dN aN
... (repeat for each test case)

Where:

• T is the number of test cases.
• For each test case, the first integer N is the number of flights.
• Each of the following N lines contains two integers representing the departure time and the arrival time of a flight.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of non-overlapping flights that can be scheduled.

The output should be written to standard output (stdout).

## sample

2
3
1 3
2 4
3 5
4
4 5
1 3
3 7
5 6

2
3

</p>