Bình là một học sinh yêu môn toán học và cũng rất hứng thú với môn Tin học. Bình rất thích thú với chương trình một cậu bạn học bên lớp chuyên tin khi chỉ cần bấm tổ hợp phím CTRL + F9 đã có ngay hàng ngàn số nguyên tố.

Bình nghĩ ra bài toán sau: CHo một dãy n số nguyên dương ~a_1, a_2, a_3, ..., a_n~

Đếm số lượng các số ~a_i~ mà ~a_i!~ (~a_i~ giai thừa là ~a_i! = 1~ x ~2~ x ~3~ x ~4~ x...x ~a_i~) chia hết cho ~a_i^2~. Bình loay hoay mãi mà vẫn chưa lập trình xong

Yêu cầu: Hãy giúp Bình lập phương trình giải bài toán trên.

Input

• Dòng đầu số n (~1 \le n \le 10^5~)
• Dòng tiếp theo ghi n số nguyên dương ~a_1, a_2, a_3, ..., a_n~(~1 \le n \le 10^9~)

Output

Số nguyên duy nhất là số lượng các số trong dãy có tính chất đã nêu

Ví dụ

Sample Input

5
10 2 4 7 6

Sample Output

2

Giải thích

Chỉ có hai số 10 và 6 có thoả mãn: 10! chia hết cho 100 và 6! chia hết cho 36

Cho số nguyên n (~1 \le n \le 10^{18}~)

Yêu cầu: Bạn hãy đưa ra một số nguyên, đó là số lượng các số từ 1 tới n thoả mãn: Số đó không chia hết cho bất kỳ số nào trong các số từ 2 đến 10.

Input

Gồm một dòng chứa số nguyên n (~1 \le n \le 10^{18}~)

Output

Số nguyên duy nhất là kết quả

Ví dụ

Sample Input

12

Sample Output

2

Giải thích

Hai số thoả mãn là 1 và 11

Cho dãy số A gồm n số hạng nguyên dương và hai số x, y nguyên dương. Dãy số U gồm m số hạng được cho bởi công thức:

• ~u_1 = x~
• ~u_i = u_{i-1} + y (i \ge 2)~

Yêu cầu: Hãy đếm xem trong dãy A có bao nhiêu số hạng vừa là số nguyên tố vừa là một số hạng nào đó trong dãy U.

Input

• Dòng đầu chứa ba số nguyên dương n, x, y ~(1 < n \le 10^5; 1 \le x, y \le 100)~
• Dòng tiếp theo chứa n số nguyên dương mô tả dãy A, mỗi số không vượt quá ~10^6~.

Output

Số lượng số hạng của dãy A thoả mãn yêu cầu trên

Ví dụ

Input

5 1 1
3 5 8 4 11

Output

3

Giải thích

Dãy U gồm các số: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 Dãy A có số 3, 5, 11 là số nguyên tố và thuộc dãy U.

Hôm nay An được học về số palindrome. Số palindrome là số mà nếu viết biểu diễn thập phân của nó (không có chữ số 0 ở đầu) ở dạng ngược lại thì ta vẫn được cùng một số.

Ví dụ, 1221 là một số palindrome trong khi 123 thì không phải.

An tò mò không biết trong đoạn từ L tới R có tất cả bao nhiêu số palindrome mà tổng chữ số ở dạng thập phân của nó là số nguyên tố. Hãy giúp An nhé.

Input

Gồm một dòng duy nhất chứa hai số nguyên L và R ~(1 \le L \le R \le 10^{12})~

Output

In ra một số nguyên duy nhất là số lượng số palindrome mà tổng chữ số ở dạng thập phân của nó là số nguyên tố trong đoạn [L, R]

Ví dụ

Sample Input

10000 12000

Sample Output

1

Giải thích

Có 9 số đó là 10001, 10101, 10301, 10501, 10901, 11111, 11311, 11711, 11911.