Longest Increasing Chain

You are given an array of integers representing heights. The task is to determine the length of the longest strictly increasing subsequence. Formally, for an array heights of length n, you must find the maximum length L such that there exists indices i₁,i₂,…,i_L with 0 \le i₁ < i₂ < \cdots < i_L < n and heights[i₁] < heights[i₂] < \cdots < heights[i_L]. One way to compute this is by dynamic programming using the recurrence

$$dp[i] = \max_{0 \le j < i \text{ and } heights[i] > heights[j]} (dp[j] + 1) $$

with the initial condition dp[i] = 1 for all valid i if the array is non-empty.

inputFormat

The first line contains an integer T indicating the number of test cases. Each test case begins with an integer N representing the number of elements in the array. The next line contains N space-separated integers representing the array heights.

outputFormat

For each test case, output a single line containing the length of the longest strictly increasing subsequence.

## sample

2
5
3 10 2 1 20
6
50 3 10 7 40 80

3
4

</p>