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à các 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ố cho trước ~k~. Đồ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?

Input

Một dòng duy nhất chứa ba số nguyên dương ~a~, ~b~ và ~k~, với:

• ~1 \le a \le b \le 10^{18}~
• ~1 \le k \le 10^{18}~

Output

Đưa ra số nguyên duy nhất là kết quả cần tìm.

Ràng buộc

• Subtask 1: 70% số test ứng với ~1 \le a \le b \le 10^{6}~
• Subtask 2: 30% số test còn lại không có ràng buộc gì thêm

Ví dụ

Input 1

3 10 5

Output 1

2

Input 2

6 9 5

Output 2

0

Một từ được định nghĩa là một kí 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ừ đó.

Cho một xâu gồm các kí tự chữ cái từ A đến Z, a đến z,chữ số từ 0 đến 9 và kí tự trắng (dấu cách).

Yêu cầu:

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

Input

Một dòng duy nhất chứa xâu có độ dài không quá 255 kí tự và trong xâu chứa ít nhất một từ.

Output

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

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 xuất hiện sau cùng trong xâu.

Ví dụ

Sample Input

Khanh_Hoa que huong toi

Sample Output

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 đến n, que thứ i có độ dài ~a_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ừ đúng 4 que tính.

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

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^6~).

Output

Ghi một 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ụ

Sample Input

7
3 8 4 3 8 1 1

Sample Output

22

Sample Input 2

5
4 9 1 9 3

Sample Output 2

-1

Ràng buộc:

• 30% số test có ~n \le 50~
• 40% số test có ~50 < n \le 1000~
• 30% số test còn lại không có ràng buộc gì thêm

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 được 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 đến 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ố.
• 31 là số nguyên tố, 3 là số nguyên tố.
• Thêm số 7 vào sau 313 thì 3137 cũng là số nguyên tố.

Yêu cầu: Cho dãy A gồm n số nguyên dương a₁, a₂, …, aₙ 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ị trí v.

Input

• Dòng đầu tiên chứa số nguyên dương n ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ ~(1 \le a_i \le 10^6)~.
• Dòng thứ ba chứa số nguyên dương m là số lượng câu hỏi ~(1 \le m \le 10^5)~.
• m dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u và v ~(1 \le u \le v \le n)~.

Output

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

Ràng buộc

• 70% số test có n, m nhỏ.
• 30% số test không có ràng buộc gì thêm.

Ví dụ

Sample Input

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

Sample Output

1
1
2