Longest Arithmetic Progression Subsequence

Given a sequence of integers, your task is to find the length of the longest subsequence that forms an arithmetic progression. An arithmetic progression is defined as a sequence in which the difference between consecutive elements remains constant. Formally, for a subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_L}\) (with \(i_1 < i_2 < \dots < i_L\)), there exists a constant \(d\) such that \(a_{i_{k+1}} - a_{i_k} = d\) for all valid \(k\).

Note: The subsequence is not required to be contiguous.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(T\), which denotes the number of test cases. For each test case, the first line contains an integer \(N\) representing the number of elements in the sequence. The next line contains \(N\) space-separated integers.

outputFormat

For each test case, output a single integer on a new line (via standard output, stdout) indicating the length of the longest subsequence that forms an arithmetic progression.

2
5
1 7 10 13 14
7
2 4 6 8 10 12 14

3
7