Nhập \(2\) số nguyên dương \(A, B\). Viết chương trình đếm xem trong đoạn [\(A, B\)] có bao nhiêu số là số nguyên tố và tất cả các chữ số của nó cũng là số nguyên tố.

Input

• Dòng đầu nhập số nguyên dương \(T\) (\(1 \leq T \leq 20\)).
• \(T\) dòng tiếp theo, mỗi dòng tiếp theo nhập \(2\) số nguyên dương \(A, B\) (\(1 \leq A \leq B \leq 10^6\)).

Output

• Với mỗi bộ test, in ra kết quả theo yêu cầu đề bài.

Example

2
10 100
1234 5678

4
26

Hãy tìm tất cả các số nguyên tố trong đoạn [\(A;B\)]

Input

• Gồm 2 số nguyên \(A;\ B\) cách nhau bởi 1 dấu cách (\(1\leq A\leq B\leq 10^7\))

Output

• Ghi ra tất cả các số nguyên tố trong khoảng [\(A;B\)]. Mỗi số trên 1 dòng.

Example

1 10

2
3
5
7

Cho dãy số nguyên (\(a_1, a_2, ..., a_n\)), \(1 \le n \le 10000\); với mọi \(i\) sao cho \(a_i \le 10^9\).

Yêu cầu:

• Hãy tìm số nguyên tố lớn nhất trong dãy trên.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\).

Output

• Dòng thứ nhất ghi số nguyên tố lớn nhất.
• Dòng thứ hai ghi các chỉ số trong dãy mà giá trị của nó là số nguyên tố lớn nhất.

Example

9
19 7 81 33 17 4 19 21 13

19
1 7

Cho đoạn thẳng trên mặt phẳng có tọa độ các điểm đầu, cuối là nguyên và là (\(x_1, y_1\)) và (\(x_2, y_2\)).

Yêu cầu:

• Hãy xác định số điểm có tọa độ nguyên nằm trên đoạn thẳng.

Dữ liệu vào

• Một dòng chứa \(4\) số nguyên \(x_1, y_1, x_2, y_2\), các số có giá trị tuyệt đối không quá \(10^8\).

Dữ liệu ra

• Một số nguyên là số điểm có tọa độ nguyên nằm trên đoạn thẳng đã cho.

-1 -2 2 4

4

Nguồn: 2019 CLQĐ-BĐ

Số nguyên dương \(x\) được gọi là một ước nguyên tố của số nguyên \(k\) nếu \(k\) chia hết cho \(x\) và \(x\) là số nguyên tố.

Yêu cầu: Nhập từ bàn phím một số nguyên dương \(k\). Hãy in ra màn hình tổng các ước nguyên tố của số \(k\).

Dữ liệu

• Số nguyên dương \(k\)

Kết quả

• Tổng các ước nguyên tố của số \(k\)

Input

21

Output

10

Ràng buộc

• Sub1: 70% test: \(k\le 10^{10}\) theo đề chuẩn
• Sub2: 30% test: \(k\le 10^{16}\) mở rộng

Nguồn: Bài 1 TS10 LQĐ TPĐN '2014

Một số nguyên dương \(n\) được gọi là một số siêu nguyên tố nếu \(n\) là số nguyên tố và khi ta
bỏ bao nhiêu chữ số tận cùng của \(n\) thì số tự nhiên mới tạo thành cũng là một số nguyên tố.

Ví dụ:

• Số 317 là số siêu nguyên tố vì số 317 là số nguyên tố, số 31 (bỏ 1 chữ số tận cùng
  của 317) là số nguyên tố, số 3 (bỏ 2 chữ số tận cùng của 317) là số nguyên tố.
• Số 61 không là số
  siêu nguyên tố vì số 6 (bỏ 1 chữ số tận cùng của 61) không là số nguyên tố.

Yêu cầu: Viết chương trình nhập vào từ bàn phím một số nguyên dương \(n\ (0 < n < 10^9)\) và
in ra màn hình một từ khẳng định số \(n\) có phải là số siêu nguyên tố hay không.

Input

• Số nguyên dương \(n\) nhập từ bàn phím (\(0 < n < 10^9\)).

Output

• In ra màn hình một từ PHAI nếu \(n\) là số siêu nguyên tố; ngược lại, in ra màn
  hình một từ KHONG nếu \(n\) không phải là số siêu nguyên tố

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n\le 10^9\) theo đề chuẩn
• Subtask \(2\) (\(30\%\) số điểm): \(n\le 10^{16}\) mở rộng

Example

317

PHAI

61

KHONG