Longest Increasing Trails Sequence

In this problem, you are given several test cases. Each test case represents a sequence of trails with various difficulty levels. Your task is to determine the length of the longest strictly increasing subsequence of trail difficulties for each test case.

Formally, for a given sequence (a_1, a_2, \dots, a_N), you need to compute the length of the longest subsequence (a_{i_1}, a_{i_2}, \dots, a_{i_k}) such that (a_{i_1} < a_{i_2} < \cdots < a_{i_k}) where (1 \leq i_1 < i_2 < \cdots < i_k \leq N). This problem can be efficiently solved using a greedy algorithm with binary search (patience sorting).

inputFormat

The input is read from standard input (stdin). The format is as follows:

• The first line contains a positive integer (T) representing the number of test cases.
  
• For each test case, the first line contains a positive integer (N) representing the number of trails.
  
• The second line contains (N) space-separated integers representing the difficulty levels of the trails.

outputFormat

For each test case, output the length of the longest strictly increasing subsequence on a new line. The output should be written to standard output (stdout).## sample

2
6
1 3 2 5 4 7
5
5 3 4 8 6

4
3