Maximum Number of Non-Overlapping Routes

You are given a set of routes for several days. Each route is defined by a start time and an end time. Your goal is to schedule as many non-overlapping routes as possible within each day. Two routes are considered non-overlapping if the start time of one route is not less than the end time of the previously chosen route. Formally, given a list of intervals \(\{(a_i, b_i)\}\), select the maximum subset such that if \(a_j\) is the start time and \(b_j\) is the finish time of a selected route, then for any two consecutive selected routes \( (a_j, b_j) \) and \( (a_k, b_k) \), it holds that \(a_k \geq b_j\).

Input Format: The first line contains an integer \(T\), the number of test cases. For each test case, the first line contains an integer \(N\), the number of routes. The following \(N\) lines each contain two space-separated integers representing the start time and the end time of a route.

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

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. For each test case, the first line contains an integer \(N\), the number of routes. This is followed by \(N\) lines, each containing two integers \(a\) and \(b\) where \(a\) is the start time and \(b\) is the end time of the route.

outputFormat

For each test case, print the maximum number of non-overlapping routes that can be scheduled, each on a new line.

## sample

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

2
3

</p>