시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 512 MB | 3 | 3 | 3 | 100.000% |
An arithmetic sequence is a sequence of numbers such that the difference between consecutive elements is constant. For example, the sequence $5, 7, 9, 11, 13$ is an arithmetic sequence (the common difference is $2$), but the sequence $1, 2, 4, 5$ is not (the differences between consecutive elements are $1$, $2$ and $1$).
Given the set of integers $\{a_1, a_2, \ldots, a_n\}$, find the size of its largest subset that forms an arithmetic sequence.
The set $A$ is said to form an arithmetic sequence if there exists an ordering of $A$ that is an arithmetic sequence.
The first line of input contains a single integer $z$, the number of test cases. The descriptions of the test cases follow.
Each test case consists of a separate line containing an integer $n$ ($1 \leq n \leq 2000$) followed by $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$). The numbers $a_i$ are pairwise distinct.
For each test case, output a single line containing the size of the largest arithmetic sequence found in the given set.
2 4 1 2 3 4 6 0 1 2 4 5 6
4 4