TLEOJ [x QTOJ] Contest #13 - G - Dãy đẹp

Điểm: 1700

Thời gian: 3.0s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Một dãy đẹp là một dãy $x_1, x_2, ..., x_k$ mà $gcd(x_i, x_{i + 1}) > 1$ với mọi $i$ .

Bạn được cho một dãy $a[1], a[2], ..., a[n]$ . Tìm một dãy $l_1 < l_2 < ... < l_k$ sao cho $k$ lớn nhất có thể và $a[l_1], a[l_2], ..., a[l_k]$ là một dãy đẹp.

Input và Output

Input: (bàn phím)

Dòng đầu tiên gồm một số nguyên dương $t$ - số bộ dữ liệu bạn cần xử lý $(1 \le t \le 10^5)$ . Tiếp theo là $t$ nhóm dòng, mỗi nhóm có dạng như sau:
- Dòng đầu tiên gồm một số nguyên dương $n$ $(1 \le n \le 10^5)$ .
- Dòng tiếp theo gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ .
Dữ liệu đầu vào đảm bảo tổng các giá trị $n$ trong các bộ dữ liệu không vượt quá $10^5$ .

Output: (màn hình)

Gồm $t$ dòng, dòng thứ $i$ là số $k$ lớn nhất có thể tìm được với bộ dữ liệu thứ $i$ .

Sample

Input (bàn phím)

Output (màn hình)

2
4

Note

Ở bộ dữ liệu đầu tiên, $(2, 4)$ là dãy đẹp dài nhất có thể tìm được.
Ở bộ dữ liệu thứ hai, $(2, 4, 6, 9)$ là dãy đẹp dài nhất có thể tìm được.

Bình luận

Không có bình luận nào.