Go Back
White Bear (250)
Description

An unknown signal began appearing on television and mobile phone screens, turning most people of the city of White Bear into passive citizens, but you and Jem are unaffected. You find out there are several transmitters and receivers placed all over the city responsible for this unknown signal. Both of you have decided to intercept the signal to stop this madness.

There are M transmitter-receiver pairs. The signals are being transmitted from the transmitter to the receiver, and the transmissions are parallel to the x-axis. The x coordinates of the each transmitter-receiver pair is denoted by x1 and x2 respectively, and each pair has a distinct y coordinate. To stop the transmission, you must transmit a ‘network-jamming’ signal, intercepting the signal transmitted by the transmitter-receiver pairs (the intercept can be made at the points x1 and x2 too) . Assume that the range of this ‘network-jamming’ signal is infinite and can intercept multiple transmissions at once. (Refer diagram for better understanding.)

Determine the least number of interceptions to be made to disrupt all the transmissions.

Input

The first line of input contains an integer T denoting the number of test cases.
The next line contains integer M, the number of transmitter-receiver pairs.
The next M lines contain two space separated integers x1 and x2.

Output

For each test case, the output is an integer N, i.e., least number of intercepts to be made.

Constraints

1 ≤ T ≤ 10
1 ≤ M ≤ 500
0 ≤ |x1| ≤ |x2| ≤ 5000

Example
Copy Input

Input:
3
3
0 2
2 4
3 5
3
1 10
11 15
16 18
5
0 5
5 10
11 15
0 2
1 3

Output:
2
3
3

Explanation

Case 1:
Here, an intercept is made at x = 2, disrupting two of the transmitter receiver pairs. Another intercept is made at x = 5, to disrupt the remaining transmitter-receiver pair.
Hence, the total number of interceptions to be made = 2.

Case 2:
Here, three separate intercepts are required; the first intercept is made anywhere in between x = 1 and x = 10, the second intercept is made anywhere in between x = 11 to x = 15, and the third one is made anywhere in between x = 16 to x = 18.
Hence, the total number of interceptions to be made = 3.

Case 3:
Here, an intercept is made at x = 2, disrupting three of the transmitter receiver pairs. An intercept is made at x = 7, to disrupt a transmitter-receiver pair. Another intercept is made at x = 12, to disrupt the remaining transmitter-receiver pair.
Hence, the total number of interceptions to be made = 3.

Single Round Match #06
3 hour contest



Announcement
Scoring will be 100-200-250.
Know more about Black Mirror: Bandersnatch here.

Problem Tags
maths, greedy

Supported by our Coding Partner