Arithmetic Sequences

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.