Dãy con chia hết

Cho số nguyên dương \(n\) và dãy số nguyên \(A = (a_1, a_2, \ldots, a_n)\).

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

Input

Dữ liệu vào có cấu trúc:

• Dòng \(1\) chứa số nguyên dương \(T\) (\(T \le 10^4\)) là số test;

• \(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\) cách nhau bởi dấu cách (\(\forall i\): \(|a_i| \le 10^6\)).
  Tổng \(n\) của tất cả các test trong một bộ dữ liệu không vượt quá \(2 \times 10^6\).

Ràng buộc:

• Subtask 1: \(40\%\) số test (\(40\%\) số điểm): \(T \le 100\) và \(n \le 100\);

• Subtask 2: \(60\%\) số test (\(60\%\) số điểm): không có ràng buộc gì thêm.

Output

In ra có cấu trúc:

• \(T\) dòng, mỗi dòng tương ứng với mỗi test, ghi ra một số nguyên duy nhất trên một dòng là độ dài 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 số \(0\).

Example

Input:

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

Output:

1
4
6
1
0

Note

• Test 1: dãy con tìm được chỉ có một phần tử, có thể chọn \(\{2\}\) hoặc \(\{3\}\);

• Test 2: dãy con tìm được là \(\{6, 12, 15, 27\}\) (cùng chia hết cho \(3\));

• Test 3: dãy con tìm được chính là dãy \(A\);

• Test 4: dãy con tìm được chỉ có một phần tử;

• Test 5: không tìm được dãy con thỏa mãn điều kiện yêu cầu.