Integers Have Friends 2.0

Problem Description

Acknowledgment: Special thanks to Codeforces Problem 1548B Integer Have Friends for providing the general statement for this problem. Indian mathematician Srinivasa Ramanujan once quoted the famous words of Indian mathematician Srinivasa Ramanujan(?) that "every positive integer was one of his personal friends." It turns out that positive integers can also be friends with each other! You are given an array $a$ of distinct positive integers. Define a subsequence $a_{c_1}, a_{c_2},\dots,a_{c_k}$ where $k\geq 1$ and $1\leq c_1<c_2<\dots<c_k\leq n$ to be a friend group if and only if there exists an integer $m\geq 2$ such that $a_{c_1}\mod m=a_{c_2} \mod m=\dots=a_{c_k} \mod m$, where $x \mod y$ denotes the remainder when $x$ is divided by $y$. Your friend gispzjz wants to know the size of the largest friend group in $a$. Can you help him?

Input

The first line contains a number $T(1\leq T\leq 30)$, denoting the number of test cases. The first line of each test case contains one integer $n(2\leq n\leq 2\times 10^5)$, denoting the size of the array $a$. Then one line containing $n$ integers $a_1,a_2,\dots,a_n(1\leq a_i\leq 4\times 10^{12})$ follow, representing the contents of the array $a$. It is guaranteed that all the numbers in $a$ are distinct.

It is guaranteed that $\sum n\leq 10^6$ over all test cases.

Output

For each test case, output a line consisting of a single integer, denoting the size of the largest friend group in $a$.

Sample Input

3

3

10 12 15

4

4 6 9 19

6

2 8 11 15 19 38

Sample Output

2

3

4

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）