Dãy con chia hết

Cho số nguyên dương \(T\) là số lượng test. Mỗi test gồm số nguyên dương \(n\) và dãy số nguyên
\(A=(a_1,a_2,\ldots,a_n)\).

Yêu cầu: Với mỗi test, hãy tìm độ dài lớn nhất của một dãy con liên tiếp của \(A\) sao cho:
tồn tại một số nguyên \(d>1\) để mọi phần tử trong dãy con đó đều chia hết cho \(d\).

Nếu không tồn tại dãy con thỏa mãn điều kiện thì in ra \(0\).

Input

• Dòng đầu chứa số nguyên dương \(T\) \((T\le 10^4)\).
• \(T\) nhóm dòng tiếp theo, mỗi nhóm gồm 2 dòng mô tả một test: - Dòng 1 chứa số nguyên dương \(n\) \((n\le 10^6)\). - Dòng 2 chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) \((|a_i|\le 10^6)\), cách nhau bởi dấu cách.

Output

Ghi ra \(T\) dòng, mỗi dòng là một số nguyên duy nhất tương ứng với mỗi test: độ dài lớn nhất của dãy con tìm được.
Nếu không tồn tại dãy con thỏa mãn điều kiện thì in ra \(0\).

Scoring

• Subtask 1 (40%): \(T\le 100\) và \(n\le 100\).
• Subtask 2 (60%): Không có ràng buộc bổ sung.

Giải thích

• Test 1: dãy con dài nhất có thể chọn là \(\{2\}\) hoặc \(\{3\}\).
• Test 2: có thể chọn \(\{6,12,15,27\}\) (cùng chia hết cho \(3\)).
• Test 3: dãy con thỏa mãn chính là cả dãy \(A\) (cùng chia hết cho \(2\)).
• Test 4: dãy con dài nhất chỉ có một phần tử.
• Test 5: không có dãy con thỏa điều kiện.

Sample Input 1

5
3
1 2 3
8
2 6 12 15 27 1 81 5
6
2 4 6 8 10 12
12
4 5 7 9 4 5 7 9 4 5 7 9
3
1 1 1

Sample Output 1

1
4
6
1
0