BOSSACT - BOSSACT

no tags 

Boss aka Baskaran is a very busy man. He has a tight schedule and is unable to manage it. He wants to do as many tasks as possible in a day. His PA and friend Nalathambi approach you to find out the maximum number of tasks he will be able to do in a day without clashing, given Boss's schedule. Help Nallathambi. Nanbaen da :)

For example, Boss's schedule:

  • 1 to 5: English class with Chandrika.
  • 6 to 9: Go to Nallathambi's shop.
  • 1 to 7: Visit his tutorial centre.
  • 2 to 5: Apply for Bank loan.
  • 8 to 12: Business meeting with Nallathambi.
  • 9 to 12: Have a peaceful sleep.

The maximum number of activities he can do here without clashing is 3.

Input

First line contains t, the number of test cases.

Then, for each test case:

First line contains n, the number of activities.

Subsequent n lines contain s, the starting time, and e, the end time of an activity.

Output

Maximum number of activities he can do.

Constraints

1 <= t <= 10

1 <= n <= 100000

0 <= s < e <= 10000

Example

Input:
2
6
1 3
2 5
3 8
5 6
6 8
8 9
4
1 3
2 4
3 4
1 4

Output:
4
2


Added by:n.7n
Date:2013-09-24
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own