Maximum Non-Overlapping Books

You are given T test cases. In each test case, you are provided with N books, and each book is represented by a pair of integers indicating its start and end times. A book can be read if its start time is greater than or equal to the end time of the previously read book. Your task is to determine the maximum number of books that can be read without overlapping intervals.

The problem can be formally defined as follows: Given a set of intervals \([s_i, t_i]\) for each test case, select the maximum number of intervals such that if \([s_i, t_i]\) and \([s_j, t_j]\) are both selected and \(i \neq j\), then they do not overlap, i.e., \(s_j \geq t_i\) (after appropriate ordering). A common strategy is to use a greedy algorithm where you first sort the books by their ending times and then select books sequentially.

inputFormat

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

T
N
s1 t1
s2 t2
... 
sN tN
... (repeated for T test cases)

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer N, the number of books.
• The next N lines each contain two integers s and t, which represent the start and end times of a book respectively.

outputFormat

For each test case, output a single integer on a new line which represents the maximum number of non-overlapping books that can be read.

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

## sample

2
3
1 4
2 5
6 8
4
1 3
4 6
6 9
10 12

2
4

</p>