Shubham is a big fan of Fibonacci. He has got a sequence of N integers. Now, he wants to choose some integers from these N integers such that after rearranging these chosen integers, the resulting sequence is a Fibonacci sequence with first 2 terms as some arbitrary integers and remaining integers follow the condition--

• $f_i = f_{i-1} + f_{i-2}$

Since, Shubham is not that good at maths, he needs your help in finding the length of longest sequence he can create from given N integers.

Input Format:

First line contains T, number of test cases.

First line of each test case contains N, number of total integers.

Second line contains N integers denoting the sequence.

Output Format:

For each test case, output the required answer in separate lines.

Constraints:

$1 \leq T \leq 5$

$2 \leq N \leq 10^3$

$1 \leq$ elements of sequence $\leq 10^9$