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 *x _{1}* and

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.

Know more about Black Mirror: Bandersnatch here.