Bài 4: Tìm phòng khách sạn

Nhân dịp Đại lễ 30/4/2026, tỉnh Ninh Bình sẽ đón lượng lớn khách du lịch quốc tế đến tham quan các địa điểm nổi tiếng như Tràng An, Tam Cốc – Bích Động, chùa Bái Đính, đền Trần, chùa Tam Chúc... Một công ty du lịch muốn lựa chọn một chuỗi khách sạn liên tiếp trên cùng một tuyến đường để đặt phòng cho một đoàn khách nước ngoài. Mỗi khách sạn được đánh giá bởi một số nguyên thể hiện mức chuẩn phục vụ quốc tế (được mã hóa bằng một số nguyên).

Để thuận tiện trong công tác tổ chức, công ty yêu cầu: Phải tồn tại một số nguyên \(d > 1\) sao cho tất cả các khách sạn trong dãy được chọn đều có mức chuẩn phục vụ chia hết cho \(d\).

Yêu cầu: Tìm độ dài lớn nhất của một dãy khách sạn liên tiếp thỏa mãn điều kiện trên. Nếu không tồn tại dãy nào thỏa mãn, in ra \(0\).

Input

• Dòng 1: Số nguyên dương \(T\) là số bộ test (\(3 \le T \le 10^4, 1 \le n \le 10^6\)).
• Với mỗi test gồm:
  • Dòng 1: Số nguyên dương \(n\) là số khách sạn trên tuyến đường.
  • Dòng 2: \(n\) số nguyên \(a_i\) (mức chuẩn phục vụ của từng khách sạn).

Output

• Với mỗi test, ghi ra một số nguyên trên một dòng là độ dài lớn nhất của dãy khách sạn liên tiếp tìm được. Nếu không tồn tại dãy thỏa mãn điều kiện, in ra \(0\).

Constraints

• \(|a_i| \le 10^6\).
• Tổng các giá trị \(n\) trong toàn bộ file không vượt quá \(10^6\).

Example

3
4
6 9 5 7
5
6 12 18 7 14
10
4 8 12 5 9 3 6 15 18 21

2
3
6

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.