Maximum Plant Cluster

You are given several test cases. In each test case, there are n plants, each with two height measurements: one from the first day and one from the second day. A cluster is defined as a subset of plants that, when sorted in increasing order of their first day heights, form a strictly increasing sequence with respect to their second day heights. In other words, after sorting the plants by their first day measurements, the task is to find the length of the longest increasing subsequence (LIS) of the second day measurements. The problem can be solved efficiently in (O(n \log n)) time using binary search techniques.

Your task is to compute the maximum plant cluster size for each test case.

inputFormat

The input is given via standard input (stdin) and consists of multiple test cases. The first line contains an integer (T) ((1 \le T \le 100)) representing the number of test cases. For each test case, the first line contains an integer (n) ((1 \le n \le 10^5)) denoting the number of plants. Then, (n) lines follow. Each line contains two integers (h_1) and (h_2) which represent the height of a plant on the first and second day respectively.

outputFormat

For each test case, output a single line containing the maximum cluster size, which is the length of the longest increasing subsequence of the second day measurements after sorting the plants by the first day height. The output should be printed via standard output (stdout).## sample

3
3
1 2
2 3
3 1
4
1 3
2 2
3 4
4 1
4
1 4
2 3
3 2
4 1

2
2
1