Số nguyên tố là số nguyên dương lớn hơn \(1\) và chỉ có đúng hai ước số dương là \(1\) và chính nó. Một số nguyên \(x\) được gọi là số nguyên tố đặc biệt nếu \(x\) là số nguyên tố và số viết ngược lại của \(x\) cũng là số nguyên tố.

Ví dụ:

• Số \(13\) là số nguyên tố đặc biệt vì \(13\) và \(31\) đều là các số nguyên tố.
• Số \(23\) không phải là số nguyên tố đặc biệt vì \(23\) là số nguyên tố nhưng \(32\) không phải là số nguyên tố.

Cho dãy số \(A\) có \(N\) phần tử nguyên \(A_1, A_2, \dots, A_N\) và \(Q\) truy vấn.

Yêu cầu

Với mỗi cặp chỉ số \(L, R\) (\(1 \le L \le R \le N\)) trong \(Q\) truy vấn, hãy đếm số lượng số nguyên tố đặc biệt trong đoạn con \(A_L, A_{L+1}, \dots, A_R\).

Dữ liệu vào (Standard Input)

• Dòng 1: Ghi hai số nguyên dương \(N, Q\) (\(1 \le N \le 10^6; 1 \le Q \le 10^6\)).
• Dòng 2: Ghi \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^7 \le A_i \le 10^7\)).
• \(Q\) dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương \(L, R\) (\(1 \le L \le R \le N\)).

Dữ liệu ra (Standard Output)

• In ra \(Q\) dòng, mỗi dòng ghi kết quả tìm được tương ứng với từng truy vấn \(L, R\).

Ví dụ