Cho dãy số nguyên \(A = (a_1, a_2, \dots, a_n)\). Hãy 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òng đầu tiên chứa số nguyên dương \(T \le 10^4\) là số lượng bộ test.
• \(T\) nhóm dòng tiếp theo, mỗi nhóm mô tả một bộ test gồm:
  • 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, \dots, a_n\) (\(|a_i| \le 10^6\)).
• Tổng các giá trị \(n\) trong tất cả các bộ test không vượt quá \(10^6\).

Output

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

Example

4
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

1
4
6
1