Đoạn đường quốc lộ ~n~ trạm đèn giao thông liên tiếp.

Mỗi trạm đèn giao thông được gán một số ~k~. Được biết khi đèn chuyển sang màu đỏ thì sẽ bắt đầu đếm ngược từ ~k~ trở về ~0~.

Khi thiết kế đoạn đường này, chính quyền sở tại đã muốn làm trải nghiệm đi đường của người dân là tốt nhất. Chính vì thế, họ mong có thể thiết kế sao cho hai trạm đèn giao thông liên tiếp luôn có thể chuyển màu xanh cùng lúc. Được biết điều này chỉ khả thi khi số đếm ~k~ trên hai đèn liên tiếp không nguyên tố cùng nhau.

• Chính quyền muốn tìm một đoạn đường dài nhất sao cho giữa hai trạm đèn giao thông liên tiếp luôn có thể chuyển màu xanh cùng lúc.
• Cụ thể hơn, chính phủ muốn tìm một đoạn đèn giao thông ~[i, j]~ có độ dài lớn nhất (~1 \leq i \leq j \leq n~) sao cho nếu ~j > i~ thì ~\forall l \in [i, j - 1]: GCD(k_l, k_{l + 1}) \ne 1~.

Yêu cầu:

Tìm đoạn đường dài nhất có các trạm đèn giao thông thỏa yêu cầu của chính phủ.

Dữ liệu (Vào từ tệp LGS.INP):

• Dòng đầu chứa số nguyên dương ~n~ (~2 \leq n \leq 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~k_i~, các số trên cùng một dòng cách nhau bởi dấu cách (~1 \leq k_i \leq 10^9~).

Kết quả (Xuất ra tệp LGS.OUT):

• Gồm một số nguyên dương duy nhất là kết quả bài toán: số lượng trạm đèn giao thông trên đoạn đường dài nhất thỏa đề.

Ví dụ:

4
4 3 6 2

3

Subtask:

• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~n \leq 400~, ~k_i \leq 400~.
• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~n \leq 10^3~.
• ~40\%~ số test còn lại tương ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Dãy số ~b_1, b_2, ..., b_k~ được gọi là dãy đẹp nếu thỏa mãn điều kiện sau: với mỗi giá trị ~b_i~ trong dãy, số lần xuất hiện của nó trong dãy là đúng ~b_i~ lần. Dãy rỗng cũng được xem là dãy đẹp.

Ví dụ

Dãy ~4, 4, 1, 2, 4, 2, 4~ là dãy đẹp vì giá trị ~4~ xuất hiện ~4~ lần, ~1~ xuất hiện ~1~ lần, ~2~ xuất hiện ~2~ lần. Dãy ~2, 5, 1, 2~ không phải là dãy đẹp vì ~5~ xuất hiện ~1~ lần.

Yêu cầu:

Cho dãy số nguyên gồm ~N~ phần tử ~a_1, a_2,….a_N~. Một thao tác cho phép ta xóa một phần tử có sẵn trong dãy, hoặc thêm một phần tử có giá trị nguyên bất kỳ vào dãy. Tìm số thao tác ít nhất để a trở thành một dãy đẹp.

Dữ liệu (Vào từ tệp DAYDEP.INP)

• Dòng đầu chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~)
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ cách nhau bởi dấu cách (~0 \leq a_i \leq 10^{9}~)

Kết quả (Xuất ra tệp DAYDEP.OUT)

Đưa ra tệp DAYDEP.OUT một số duy nhất là số lượng thao tác ít nhất cần thực hiện để dãy trở thành dãy đẹp.

Ví dụ

5
2 5 1 2 5

2

Subtask

• ~20\%~ số test tương ứng với ~20\%~ số điểm có ~a_i \leq 5~.
• ~40\%~ số test tương ứng với ~40\%~ số điểm có ~a_i \leq 10^6~.
• ~40\%~ số test còn lại tương ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Mã hóa - ENCRYPTION

Khi nghiên cứu xây dựng thuật toán mã hóa, Nam cần giải quyết bài toán sau: Với bốn số nguyên dương ~L, R, A, K,~ cần đếm số lượng số nguyên dương ~S~ mà ~L ≤ S ≤ R~ và ~(A * S)~ ~mod~ ~K~ ~= 0~, trong đó ~mod~ là phép toán chia lấy dư.

Hãy giúp Nam giải bài toán trên.

Yêu cầu:

Đếm số lượng số nguyên dương ~S~ thỏa yêu cầu bài toán

Dữ liệu (Vào từ tệp ENCRYPTION.INP):

• Dòng duy nhất chứa ~4~ số nguyên dương ~L, R, A, K~ ~(1 ≤ L, R, A, K ≤ 10^{18}; L ≤ R)~.

Kết quả (Xuất ra tệp ENCRYPTION.OUT):

• Gồm một số nguyên dương duy nhất là kết quả bài toán

Ví dụ:

1 10 2 10

2

Subtask:

• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~1~ ~≤ L, R, K ≤~ ~10^6~ và ~A = 1~.
• ~40\%~ số test tương ứng với ~40\%~ số điểm có ~1~ ~≤ L, R, A, K ≤~ ~10^6~.
• ~30\%~ số test còn lại tương ứng với ~30\%~ số điểm không có ràng buộc gì thêm.