Longest Increasing Subsequence

Given an integer sequence (a_{1}, a_{2}, \dots, a_{n}), your task is to compute the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

For example, in the sequence [1, 2, 1, 5, 6], one valid longest increasing subsequence is [1, 2, 5, 6] which has a length of 4.

inputFormat

The first line contains an integer (T), denoting the number of test cases. Each test case consists of two lines: the first line contains an integer (N), the number of elements in the sequence, and the second line contains (N) space-separated integers.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest strictly increasing subsequence.## sample

5
5
1 2 1 5 6
8
10 9 2 5 3 7 101 18
6
1 2 3 4 5 6
6
6 5 4 3 2 1
8
10 5 8 3 7 9 1 2

4
4
6
1
3