536. Get it Done

0

Medium

Aryan has a busy weekend ahead with a lot of pending tasks. He wants to complete as many tasks as possible, considering each task's start and end times. Once he starts a task, he cannot switch to another task until completing the current one. Your task is to assist Aryan in maximizing the number of tasks he can complete. Please note that there are multiple test cases in this problem.

Input Format

The first line of input contains an integer T, representing the number of test cases. For each test case, the first line contains an integer N, representing the number of activities. The next N lines contain two integers m and n, representing the start and end times of each activity.

Output Format

For each test case, output the maximum number of activities that can be completed.

Example

Input

3
3
3 9
2 8
6 9
4
1 7
5 8
7 8
1 8
6
7 9
0 10
4 5
8 9
4 10
5 7

Output

1
2
3

Constraints

1 <= T <=10

1 <= N <= 100000

0 <= start < end <= 1000000

1 <= N <= 100000

0 <= start < end <= 1000000

Loading...

View Submissions

Console