Longest Arithmetic Progression Subsequence

Given an array of integers, determine the length of the longest subsequence which forms an arithmetic progression. An arithmetic progression is defined as a sequence of numbers where the difference between consecutive terms is constant. Formally, for a subsequence a_i1, a_i2, ..., a_ik (with i₁ < i₂ < ... < i_k), it is an arithmetic progression if there exists a constant d such that

$$a_{i+1}-a_{i} = d$$

Your task is to compute the maximum possible length of such a subsequence for each test case.

Input begins with an integer T representing the number of test cases. For each test case, the first line contains an integer N, the number of elements in the array, followed by a line with N space-separated integers. The result for each test case should be printed on a new line.

inputFormat

The first line contains an integer T, representing the number of test cases. For each test case:

• The first line contains an integer N, denoting the number of elements in the array.
• The second line contains N space-separated integers.

Use standard input (stdin) to read the input.

outputFormat

For each test case, output the length of the longest arithmetic progression subsequence on a separate line using standard output (stdout).

## sample

2
6
1 7 10 15 27 29
7
5 10 15 20 25 30 35

3
7

</p>