Nấm là cô bé đáng yêu và tốt bụng. Cô bé đặc biệt thích truyện cổ tích. Vì thế, đêm qua, Nấm nằm mơ về nàng Lọ Lem. Trong giấc mơ, Lọ Lem không bị mụ dì ghẻ bắt phân loại các loại đậu nữa mà bắt nhặt gạo. Có rất nhiều gạo trong kho, các hạt gạo đã được đánh số thứ tự là số nguyên liên tiếp từ a tới b Mụ bắt nàng phải nhặt ra các hạt gạo có số thứ tự là bội của một số k cho trước.

Đồng thời sau khi nhặt xong phải trả lời cho mụ biết số lượng hạt gạo nhặt được. Việc nhặt gạo thì quá đơn giản, chỉ trong tích tắc bầy chim đã giúp nàng nhặt xong. Bây giờ nhiệm vụ của Nấm là đếm số lượng hạt gạo đã nhặt được. Thật không may, chưa đếm xong thì Nấm đã tỉnh dậy.

Nấm rất muốn có câu trả lời cho Lọ Lem.

Yêu cầu : Hãy trả lời giúp Nấm, nếu hoàn thành phần việc của mình, Nấm sẽ đếm được bao nhiêu hạt gạo?

Đầu vào

1 Dòng duy nhất chứa 3 số a, b, k.

Giới hạn

• 1 ≤ a ≤ b ≤ 10^18; 1 ≤ k ≤ 10^18

• 70% số test tương ứng với 70% số điểm có 1 ≤ a ≤ b ≤ 10^6.

• 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm

Đầu ra

In ra kết quả cần tìm

Ví dụ :

Input 01

3 10 5

Output 01

2

Giải thích test :

Hai hạt gạo được nhặt là hạt có số thứ tự 5 và hạt gạo số thứ tự 10.

Một từ được định nghĩa là một hoặc một dãy các kí tự liên tiếp nhau và không chứa dấu cách (kí tự trắng).

Độ dài của một từ là số kí tự có trong từ đó.

Yêu cầu : Tìm độ dài của từ có nhiều kí tự nhất và từ tương ứng với độ dài đó.

Lưu ý: nếu có nhiều từ có cùng độ dài lớn nhất thì ghi từ có độ dài lớn nhất sau cùng trong xâu.

Đầu vào

Gồm 1 dòng duy nhất chứa xâu (độ dài xâu không quá 255 kí tự và trong xâu chứa ít nhất một từ).

Giới hạn

Xâu chỉ gồm ký tự là chữ cái hoặc chữ số, dấu cách.

Đầu ra

• Dòng 1: Ghi độ dài của từ có nhiều kí tự nhất (độ dài lớn nhất).

• Dòng 2: Ghi từ có độ dài lớn nhất.

Ví dụ :

Input 01

que huong toi

Output 01

5
huong

Tí đang chơi trò ghép nhà từ những que tính. Phần căn nhà đã được ghép xong, chỉ còn thiếu một cửa sổ hình chữ nhật. Hiện tại, Tí còn dư n que tính, các que tính được đánh số thứ tự từ 1 tới n que thứ i có độ dài a[i] (đơn vị đo chiều dài). Tí muốn ghép được cửa sổ càng to càng tốt. Một cửa sổ sẽ được ghép từ 4 que tính.

Yêu cầu: Hãy cho biết chu vi của cửa sổ lớn nhất mà Tí có thể ghép được.

Lưu ý: Không bẻ gãy hay chắp nối để thay đổi chiều dài que tính và hình vuông cũng được xem là hình chữ nhật.

Đầu vào

• Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 10^6).

• Dòng thứ hai chứa n số nguyên dương a[i] (1 ≤ a[i] ≤ 10^6; 1 ≤ i ≤ n)

Giới hạn

• 30% số test tương ứng với 30% số điểm có n ≤ 50.

• 40% số test tương ứng với 40% số điểm có 50 < n ≤ 1000.

• 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.

Đầu ra

In số nguyên duy nhất là chu vi lớn nhất của cửa sổ có thể ghép được. Nếu không thể ghép được thì ghi -1.

Ví dụ :

Input 01

7
3 8 4 3 8 1 1

Output 01

22

Giải thích test :

Có 3 cách ghép thành cửa sổ là cửa sổ có chiều dài và chiều rộng như sau: (8, 3); (3, 1); (8, 1) Chu vi lớn nhất là (3 + 8) × 2 = 22

Input 02

5
4 9 1 9 3

Output 02

-1

Giải thích test :

Không thể ghép thành cửa sổ nào cả.

Hôm nay, An được học về số nguyên tố. Số nguyên tố là số có đúng hai ước nguyên dương là 1 và chính nó. Ví dụ số 17 là số nguyên tố nhưng số 16 thì không.

Vốn là người có nhiều ý tưởng sáng tạo, An đưa ra một khái niệm mới gọi là số nguyên tố toàn diện. Một số nguyên dương x gọi là số nguyên tố toàn diện nếu thỏa mãn đồng thời 3 điều kiện sau:

• x là số nguyên tố.

• Lần lượt bỏ đi các chữ số bên phải của x thì phần còn lại của nó vẫn là số nguyên tố.

• Thêm vào bên phải của x một trong các chữ số từ 0 tới 9, số thu được cũng là số nguyên tố.

Ví dụ số 313 là số nguyên tố toàn diện vì:

• 313 là số nguyên tố.

• Bỏ đi số 3 bên phải ta còn số 31 là số nguyên tố, bỏ tiếp số 1 ta còn số 3 cũng là số nguyên tố.

• Thêm số 7 vào sau 313 ta được số 3137 là số nguyên tố.

Yêu cầu: Cho dãy A gồm n số nguyên dương a[1], a[2], ... a[n] và m câu hỏi. Mỗi câu hỏi có dạng (u v với ý nghĩa: Đếm số lượng số nguyên tố toàn diện trong dãy A từ vị trí u tới v

Đầu vào

• Dòng đầu chứa số nguyên n (1 ≤ n ≤ 10^5).

• Dòng thứ hai chứa n số nguyên dương trong dãy A (1 ≤ a[i] ≤ 10^6

• Dòng thứ ba chứa số nguyên m là số lượng câu hỏi (1 ≤ m ≤ 10^5).

• m dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v (1 ≤ u ≤ v ≤ n)

Giới hạn

• 70% số test tương ứng với 70% số điểm có 1 ≤ n ≤ 10^3; 1 ≤ a[i] ≤ 103^; 1 ≤ m ≤ 10^3.

• 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.

Đầu ra

In ra m dòng, mỗi dòng là đáp án của một câu hỏi theo thứ tự của các câu hỏi được đưa ra

Ví dụ :

Input 01

6
59 12 57 53 23 313
3
1 3
2 5
3 6

Output 01

1
1
2

Giải thích test :

• Có 1 số nguyên tố toàn diện là 59 trong đoạn từ 1 tới 3.

• Có 1 số nguyên tố toàn diện là 23 trong đoạn từ 2 tới 5.

• Có 2 số nguyên tố toàn diện là 23 và 313 trong đoạn từ 3 tới 6.