Cho một số nguyên dương ~N~, gọi ~M~ là tập các số nhận được từ ~N~ bằng cách giữ nguyên hoặc xóa đi một số chữ số của ~N~.

Ví dụ với ~N = 2301~ thì ~M = {0; 1; 2; 3; 20; 21; 23; 30; 31; 201; 230; 231; 301; 2301}~.

Yêu cầu: Tìm số lớn nhất trong tập ~M~ là số nguyên tố.

INPUT

Một dòng duy nhất chứa số nguyên dương ~N~ (~N \le 10^{14}~)

OUTPUT

Một dòng duy nhất, chứa số nguyên tố lớn nhất trong tập ~M~, nếu không có số nguyên tố nào trong tập ~M~ thì ghi ra ~-1~.

SAMPLE INPUT

2301

SAMPLE OUTPUT

31

Cho số nguyên dương ~n~ (~n~ ~\le~ ~10^{18}~), hãy đưa ra số lượng các số từ ~1~ đến ~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

Dòng đầu tiên chứa số nguyên dương ~t~ (~t~ ~\le~ ~10^5~) là số test của đề bài

~t~ dòng tiếp theo, mỗi dòng chứa số nguyên dương ~n~ (~n~ ~\le~ ~10^{18}~)

OUTPUT

Đưa ra ~t~ dòng, mỗi dòng một số nguyên, là số các số từ ~1~ đến ~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~

SAMPLE INPUT

1
12

SAMPLE OUTPUT

2

Cho ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Với mỗi số ~a_i~, hãy kiểm tra xem ~a_i~ có phải số nguyên tố không?

INPUT

Gồm ~n~ dòng, dòng thứ ~i~ là số nguyên dương ~a_i~. (~n \le 10^5~, ~1 \le a_i \le 2^{53}~)

OUTPUT

Gồm ~n~ dòng, dòng thứ ~i~ ghi ra ~1~ nếu số ~a_i~ là số nguyên tố, ngược lại ghi ra ~0~.

SAMPLE INPUT

3
5
6

SAMPLE OUTPUT

1
1
0

Bạn được nhận ~k \le 7~ chữ số ngẫu nhiên.

Yêu cầu: Dùng các chữ số bạn nhận được, hãy đếm xem có thể tạo ra được bao nhiêu số nguyên tố khác nhau.

Input

• Dòng đầu tiên là số ~T \le 10~ - số lượng test.
• ~T~ dòng tiếp theo, mỗi dòng gồm ~k~ chữ số tương ứng với một yêu cầu.

Output

• ~T~ dòng là kết quả của các test tương ứng theo thứ tự.

Sample Input 1

2
17
9999999

Sample Output 1

3
0

Giải thích

• Với ~2~ chữ số ~1,7~, tạo ra được 3 số nguyên tố là ~7, 17, 71~.
• Với ~7~ chữ số ~9~, không tạo ra được số nguyên tố nào.

Số siêu nguyên tố là số nguyên tố có tổng các chữ số cũng là số nguyên tố. Ví dụ: số ~5, 23~ là số siêu nguyên tố.

Hãy đếm số số siêu nguyên tố trong đoạn ~m, n \le 10^6~

INPUT

2 số nguyên dương ~m~, ~n~ (~0~ ~\le~ ~m~, ~n~, ~\le~ ~10^6~)

OUTPUT

Số nguyên dương duy nhất thoả mãn yêu cầu đề bài

SAMPLE INPUT

5 20

SAMPLE OUTPUT

3

Cho số ~n~. Hãy tìm số ~k \le n~ lớn nhất sao cho ~k~ là tích của 3 số nguyên tố liên tiếp.

Input

• Gồm số tự nhiên ~n \le 10^{18}~.

Output

• Gồm duy nhất một số tự nhiên ~k~. Nếu không có số thỏa mãn in ra -1.

Sample Test

Input:

31

Output

30