Longest Increasing Subsequence

Given an array of integers, your task is to find the length of the longest increasing subsequence (LIS) in the array.

The Longest Increasing Subsequence of an array is defined as the longest sequence of indices \( i_1, i_2, \dots, i_k \) such that \( A[i_1] < A[i_2] < \dots < A[i_k] \). A subsequence is not necessarily contiguous, but the order of elements should be maintained.

Your solution should be efficient with a time complexity of \( O(n \log n) \) for each test case. Use binary search (e.g. bisect_left in Python or std::lower_bound in C++) to achieve this efficiency.

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases.

Each test case begins with an integer \(N\) (the number of elements in the array), followed by a line containing \(N\) space-separated integers representing the array.

Input is read from stdin.

outputFormat

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

Output should be written to stdout.

## sample

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

3
5

</p>