Bài 4. Dãy con cùng chia hết cho một số

Cho số nguyên dương ~n~ và dãy số nguyên ~A = (a_1, a_2, ..., 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~ sao cho tồn tại một số nguyên ~d > 1~ và mọi phần tử trong dãy con đó đều chia hết cho ~d~.

Dữ liệu vào

Dữ liệu được đọc từ tệp văn bản BAI4.INP theo cấu trúc:

• Dòng 1 chứa số nguyên dương ~T~, là số lượng bộ dữ liệu.
• ~T~ nhóm dòng tiếp theo, mỗi nhóm gồm 2 dòng mô tả một bộ dữ liệu:
  • Dòng 1 chứa số nguyên dương ~n~.
  • Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách.

Dữ liệu ra

Kết quả được ghi vào tệp văn bản BAI4.OUT. Gồm ~T~ dòng, mỗi dòng ghi một số nguyên duy nhất là độ dài dãy con tìm được tương ứng với một bộ dữ liệu. Nếu không tồn tại dãy con thỏa mãn thì ghi 0.

Ví dụ

Giải thích:

• 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}.
• Test 3: Dãy con tìm được chính là toàn bộ 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 yêu cầu.

Giới hạn

• ~T ≤ 10^4~.
• Với mỗi bộ dữ liệu, ~n ≤ 10^6~.
• Với mọi ~1 ≤ i ≤ n~, ~|a_i| ≤ 10^6~.
• Subtask 1: ~T ≤ 100~ và ~n ≤ 100~.
• Subtask 2: Không có ràng buộc bổ sung.