Longest Arithmetic Subsequence

You are given a sequence of integers. Your task is to find the length of the longest subsequence that forms an arithmetic progression. In other words, you need to select a subsequence \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) (with \(i_1 < i_2 < \cdots < i_k\)) such that the differences \(a_{i_2}-a_{i_1}, a_{i_3}-a_{i_2}, \ldots, a_{i_k}-a_{i_{k-1}}\) are all equal. Note that the subsequence does not have to be contiguous in the original sequence.

Input/Output Format:

The input begins with an integer \(T\) representing the number of test cases. For each test case, the first number is an integer \(N\) (the length of the sequence) followed by \(N\) space-separated integers.

For each test case, output the length of the longest arithmetic subsequence on a new line.

Example:

For the sequence 10 7 4 6 8 10 11 (with \(N = 7\)), one of the longest arithmetic subsequences is 4 6 8 10 with common difference \(2\). Hence, the answer is 4.

inputFormat

The first line of the input contains an integer \(T\), denoting the number of test cases. This is followed by \(T\) test cases. For each test case, the first number is an integer \(N\) representing the size of the sequence, followed by \(N\) space-separated integers.

Example:

3
7 10 7 4 6 8 10 11
6 1 7 3 5 9 11
6 1 2 3 4 5 6

outputFormat

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

Example:

4
3
6

## sample

3
7 10 7 4 6 8 10 11
6 1 7 3 5 9 11
6 1 2 3 4 5 6

4
3
6

</p>