Maximum Number of Non-Overlapping Workshops

Kavi has a list of workshops, each defined by its start time and finish time. Two workshops are considered non-overlapping if the start time of one is not earlier than the finish time of the other. Your task is to determine the maximum number of workshops that can be organized without any overlaps.

More formally, given a set of intervals ( [a_i, b_i] ) for ( i=1,2,\ldots,N ), select the maximum subset such that for any two intervals ( [a_i, b_i] ) and ( [a_j, b_j] ) in the subset (with ( i \neq j )), the condition ( a_j \geq b_i ) (or vice-versa) holds. This is a classic greedy algorithm problem.

inputFormat

The first line of the input contains an integer ( T ) denoting the number of test cases. For each test case, the first line contains an integer ( N ) representing the number of workshops. The following line contains ( 2N ) integers where each consecutive pair represents the start time and finish time of a workshop.

Example:

2 1 1 2 2 1 5 6 10

outputFormat

For each test case, output a single line containing one integer: the maximum number of non-overlapping workshops that can be organized.## sample

1
3
1 2 3 4 5 7

3