Longest Consecutive Sequence

You are given an array of integers. Your task is to find the length of the longest subsequence of consecutive integers that can be formed using the numbers in the array. Note that the elements of the consecutive subsequence do not need to be adjacent in the original array.

For example, given the array [2, 6, 1, 9, 4, 5, 3], the longest consecutive subsequence is [1, 2, 3, 4, 5, 6] with length 6.

Hint: A optimal approach uses a hash set to achieve an average time complexity of \(O(n)\), where \(n\) is the number of elements in the array.

inputFormat

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

For each test case, the first line contains an integer \(N\) representing the number of elements in the array. The second line contains \(N\) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single integer on a new line denoting the length of the longest consecutive subsequence in the given array.

## sample

3
7
2 6 1 9 4 5 3
6
1 9 3 10 4 20
5
1 2 3 4 5

6
2
5

</p>