Longest Arithmetic Progression Subsequence

You are given an array of n integers. Your task is to find the length of the longest subsequence in which the differences between consecutive elements are constant, i.e., an arithmetic progression (AP). Formally, for a subsequence a_i1, a_i2, ..., a_ik (with i1 < i2 < ... < ik), it must hold that:

\(a_{i2} - a_{i1} = a_{i3} - a_{i2} = \cdots = a_{ik} - a_{i(k-1)}\)

Your solution should read input from standard input (stdin) and output the answer for each test case to standard output (stdout).

inputFormat

The input begins with an integer T representing the number of test cases. For each test case:

• The first line contains an integer n, the size of the array.
• The second line contains n space-separated integers.

outputFormat

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

## sample

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

3
5

</p>