Given an array A, find the length of the longest strictly increasing subsequence (LIS).

A subsequence is a sequence that can be derived from an array by deleting some or no elements such that the order of the remaining elements remain the same.

Example

A: [10, 20, 2, 5, 3, 8, 8, 25, 6]
Result: 4
Explanation: Longest increasing subsequence: [2, 5, 8, 25]

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has two lines:

• An integer ‘n’ denoting the length of the array A.
• n space-separated integers denoting the elements of the array A.

Output Format

For each test case, the output contains a line with one integer denoting the length of the longest increasing subsequence.

Sample Input

5
9
10 20 2 5 3 8 8 25 6
7
10 -63 7 -50 32 -9 -3
7
71 0 4 42 -31 4 -42
6
77 0 -2 25 1 70
7
2 2 1 5 7 -50 80

Expected Output

4
4
3
3
4

Constraints

1 <= T <= 10
1 <= n <= 3000
-109 <= Ai <= 109