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 subsequenceac1,ac2,…,ack where k≥1 and 1≤c1<c2<⋯<ck≤n to be a friend group if and only if there exists an integer m≥2 such that ac1 mod m=ac2 mod m=⋯=ack 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≤T≤30), denoting the number of test cases.
The first line of each test case contains one integer n(2≤n≤2×105), denoting the size of the array a.
Then one line containing n integers a1,a2,…,an(1≤ai≤4×1012) follow, representing the contents of the array a. It is guaranteed that all the numbers in a are distinct.
It is guaranteed that ∑n≤106 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.