Xâu kí tự ~S~ được gọi là xâu Palindrome khi đọc các kí tự từ trái sang phải và từ phải sang trái là như nhau.

Ví dụ: Các xâu abcba, a, bbbb là các xâu Palindrome; các xâu abcabc, abca không phải là xâu Palindrome.

Yêu cầu

Cho ~N~ xâu kí tự, hãy đếm số lượng các xâu Palindrome.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng thứ nhất ghi số nguyên dương ~N~ ~(N \le 10^4)~ là số lượng các xâu kí tự.
• ~N~ dòng tiếp theo, mỗi dòng ghi một xâu gồm các kí tự trong tập a..z, có độ dài không quá ~255~ kí tự.

Dữ liệu đầu ra

Gồm một số nguyên ~t~ duy nhất là số lượng xâu Palindrome tìm được.

Ví dụ

Ví dụ 1

INPUT

3
abcba
abcabc
cdc

OUTPUT

2

Cho số nguyên dương ~N~ và dãy ~a~ gồm ~N~ số nguyên dương ~a_1, a_2,..., a_N~.

Một dãy được gọi là dãy con của ~a~ nếu nó được tạo ra bằng cách lấy ra ~k~ phần tử liên tiếp trong ~a~ ~(k \ge 1)~.

Yêu cầu

Tìm dãy con dài nhất của ~a~ sao cho tất cả các phần tử trong dãy đều là số nguyên tố.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~N~ ~(1 \le N \le 10^5)~ là số lượng phần tử của dãy ~a~.
• Dòng thứ hai ghi dãy ~a~ gồm ~N~ số nguyên dương ~a_1, a_2,..., a_N~ ~(1 \le a_i \le 10^6;\ 1 \le i \le N)~, các số được ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên ~t~ duy nhất là độ dài của dãy con tìm được theo yêu cầu. Trường hợp không tồn tại dãy con nào thỏa mãn thì ghi số ~0~.

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm: ~N \le 10^3;\ a_i \le 10^3~
• Có 40% số test ứng với 40% số điểm: không có ràng buộc gì thêm

Ví dụ

Ví dụ 1

INPUT

6
1 5 2 3 4 5

OUTPUT

3

Ví dụ 2

INPUT

6
1 4 8 9 12 6

OUTPUT

0

Một trò chơi gồm có ~N~ màn chơi, các màn chơi được đánh số từ ~1~ đến ~N~, màn chơi thứ ~i~ có mã số ~a_i~ và chi phí là ~b_i~ ~(1 \le i \le N)~. Bạn chỉ được phép chọn một dãy liên tiếp các màn chơi từ vị trí ~l~ đến vị trí ~r~ thỏa mãn các điều kiện sau:

• Tại mỗi màn chơi thứ ~i~ ~(1 \le l \le i < r \le N)~, ~a_i~ luôn chia hết cho ~a_{i + 1}~.
• Tổng chi phí các màn chơi từ vị trí ~l~ đến vị trí ~r~ ~(b_i + b_{i + 1} + \ldots + b_r)~ không vượt quá số nguyên dương ~k~ cho trước.

Yêu cầu

Tìm cách chọn sao cho số lượng các màn chơi là nhiều nhất.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng thứ nhất ghi hai số nguyên dương ~N, k~ ~(2 \le N \le 2 \times 10^5;\ 1 \le k \le 10^9)~.
• Dòng thứ hai ghi ~N~ số nguyên dương ~a_1, a_2,..., a_N~ ~(1 \le a_i \le 10^9;\ 1 \le i \le N)~.
• Dòng thứ ba ghi ~N~ số nguyên dương ~b_1, b_2,..., b_N~ ~(1 \le b_i \le 10^5;\ 1 \le i \le N)~.

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên ~t~ duy nhất là số lượng màn chơi nhiều nhất mà bạn có thể chơi. Trường hợp không tìm được dãy màn chơi nào thỏa mãn thì ghi số ~0~.

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm: ~N \le 10^3~.
• Có 40% số test ứng với 40% số điểm: không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4 8
6 2 3 1
5 4 1 2

OUTPUT

2

Ví dụ 2

INPUT

4 8
6 2 3 2
5 4 1 2

OUTPUT

0

Đất nước ABC có ~N~ thành phố được đánh số thứ tự từ ~1~ đến ~N~ và ~m~ con đường hai chiều trực tiếp nối các thành phố với nhau. Hiện tại các con đường giữa các thành phố đang được nâng cấp, con đường hai chiều thứ ~i~ nối hai thành phố ~u_i, v_i~, và sẽ được khánh thành vào ngày ~d_i~. Các thành phố luôn có đường đi đến với nhau (trực tiếp hoặc gián tiếp), giữa hai thành phố bất kì chỉ có nhiều nhất một con đường hai chiều trực tiếp nối chúng và không có đường đi nối một thành phố với chính nó.

Yêu cầu

Có ~q~ đoàn khách du lịch đến tham quan đất nước ABC. Đoàn khách thứ ~i~ đang ở thành phố ~a_i~ có nhu cầu đi tham quan thành phố ~b_i~. Bạn hãy giúp các đoàn biết sớm nhất là ngày bao nhiêu thì đường đi từ thành phố ~a_i~ đến thành phố ~b_i~ được thông suốt để đoàn có thể khởi hành. Chú ý rằng nếu thành phố đang ở và thành phố muốn đến tham quan trùng nhau ~(a_i = b_i)~ thì đoàn có thể đi ngay được luôn nên quy ước ngày đi sẽ là ngày ~0~.

Dữ liệu đầu vào

Gồm ~m + q + 1~ dòng:

• Dòng thứ nhất ghi ba số nguyên dương ~N, m, q~ lần lượt là số lượng thành phố, số lượng con đường trực tiếp và số lượng đoàn khách du lịch ~(1 \le N, q \le 10^5;\ 1 \le m \le 2 \times 10^5)~
• ~m~ dòng tiếp theo, dòng thứ ~i~ ghi ba số nguyên dương ~u_i, v_i, d_i~ mô tả con đường hai chiều thứ ~i~ nối hai thành phố ~u_i, v_i~, và sẽ được khánh thành vào ngày ~d_i~ ~(1 \le u_i, v_i \le N;\ 1 \le d_i \le 10^9)~
• ~q~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên dương ~a_i, b_i~ lần lượt là thành phố đang ở và thành phố mà đoàn khách thứ ~i~ muốn đến tham quan ~(1 \le a_i, b_i \le N)~

Chú ý: Các số trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm ~q~ dòng, dòng thứ ~i~ ghi số nguyên ~t_i~ là ngày sớm nhất mà đường đi từ thành phố ~a_i~ đến thành phố ~b_i~ được thông suốt.

Ràng buộc dữ liệu

• Có 50% số test tương ứng với 50% số điểm: ~N, m, q \le 200~.
• Có 25% số test tương ứng với 25% số điểm: ~N, m, q \le 2000~.
• Có 25% số test tương ứng với 25% số điểm: không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5 7 4
1 3 1
2 3 2
4 1 6
4 3 5
5 2 7
1 5 1
4 5 4
1 2
4 5
5 3
1 5

OUTPUT

2
4
1
1