Longest Arithmetic Subsequence

Given an array of integers, your task is to determine the length of the longest arithmetic subsequence within the array. An arithmetic subsequence is defined as a sequence of numbers (a_1, a_2, \dots, a_k) (not necessarily contiguous) where the difference between consecutive elements is constant, i.e. (a_{i+1} - a_{i} = d) for every (1 \leq i < k).

For example, in the array [1, 7, 10, 15, 27], one possible arithmetic subsequence is [1, 7] with a common difference of 6. Your solution should efficiently compute the maximum length of any such subsequence in the given array.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) denoting the number of test cases. Each test case begins with an integer (N) representing the number of elements in the array, followed by (N) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line containing one integer: the length of the longest arithmetic subsequence in the array. The output is written to standard output (stdout).## sample

2
5
1 7 10 15 27
6
1 5 7 8 5 15

2
3