Đề bài

Với hai số nguyên dương \(k, p\), số \(p\) được gọi là số \(prime^k\) nếu một trong các số \(p - k, p - k + 1, ..., p, ..., p + k\) là số nguyên tố.

Ví dụ: các số \(4, 5, 10\) là \(prime^1\) vì tồn tại ít nhất một số nguyên tố trong đoạn \([p - 1, p + 1]\).

Yêu cầu: Cho \(n\) cặp số nguyên dương, với cặp thứ \(i\) là \((k_i, p_i)\), hãy xác định xem \(p_i\) có phải là số \(prime^{k_i}\) hay không.

Dữ liệu vào

• Dòng đầu chứa một số nguyên \(n\) — số lượng truy vấn.
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(k_i, p_i\).

Giới hạn:

• \(1 \leq i \leq n\)
• \(k_i \leq p_i \leq 10^6\)

Dữ liệu ra

• Gồm \(n\) dòng, dòng thứ \(i\) in ra:
  • \(1\) nếu \(p_i\) là số \(prime^{k_i}\);
  • \(0\) nếu không phải.

Giới hạn

• Subtask 1 (50%): \(n = 1; k_1 = 1\)
• Subtask 2 (25%): \(n = 1\)
• Subtask 3 (25%): \(n \leq 10^6\)

Sample Input 1

4
1 15
1 4
1 81
2 81

Sample Output 1

0
1
0
1