시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 2 2 2 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.

예제 입력 1

2
4 1 2 3 4
6 0 1 2 4 5 6

예제 출력 1

4
4