Maximum Number of Non-Overlapping Segments

You are given several test cases. Each test case consists of a number of segments. Each segment is described by two integers, representing the start and end points. Two segments are considered non-overlapping if for a segment with start (L) and end (R) and the previously chosen segment with end R'_last, the condition \(L > R_{last}\) holds.

Your task is to determine, for each test case, the maximum number of segments that can be selected such that no two segments overlap. The greedy strategy to solve this problem is to sort the segments by their end points (R) and then iteratively select segments that start after the end of the last selected segment.

Note: All formulas and conditions are formatted in LaTeX when needed. The condition for non-overlapping segments is: \(L_i > R_{last}\), where \(L_i\) is the starting point of the current segment and \(R_{last}\) is the ending point of the last selected segment.

inputFormat

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

T
N1
L11 R11
L12 R12
... 
L1N1 R1N1
N2
L21 R21
... 
L2N2 R2N2
...
NT
L T1 R T1
... 
L TN T RN T

Here, T is the number of test cases. For each test case, the first number is N which indicates the number of segments. Then, for each test case, N lines follow, each line containing two integers representing the starting and ending points of a segment.

outputFormat

For each test case, output a single line containing the maximum number of non-overlapping segments that can be selected. The output is written to stdout.

## sample

4
3
1 3
2 5
4 6
4
7 9
1 5
3 4
2 8
3
1 2
3 4
5 6
6
1 3
3 5
4 6
5 7
6 8
7 9

2
2
3
3

</p>