#52. Dãy con chia hết (Mã bài: SUBSEQ)

Cho dãy số nguyên gồm phần tử . 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 dãy số thỏa mãn: Tồn tại một số nguyên dương sao cho mọi phần tử trong dãy con đó đều chia hết cho .

Dữ liệu:

• Dòng đầu: số nguyên — số test ().
• Với mỗi test:
  • Dòng 1: số nguyên ().
  • Dòng 2: số nguyên ().

Kết quả: Ghi ra dòng, mỗi dòng là độ dài dãy con dài nhất tìm được. Nếu không tồn tại, in ra 0.

Ví dụ:

Dữ liệu:

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

Kết quả:

4
6
1

Giới hạn: .

• Subtask #1: 20% số điểm với .
• Subtask #2: 30% số điểm với .
• Subtask #3: 50% số điểm còn lại không có ràng buộc thêm.