**Nguyên tố (nguyentobn.*)**

Số nguyên tố là số nguyên dương lớn hơn 1 và có đúng hai ước số dương là 1 và chính nó. Một số nguyên dương \(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ảu \(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à 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},\ldots,a_{n}\) và một số nguyên dương \(q\).

Yêu cầu: với mỗi cặp chỉ số \(l,\ r\ (1 \leq l \leq r \leq n)\) trong \(q\) truy vấn, đếm số lượng số nguyên tố đặc biệt trong đoạn còn \(a_{l},\ a_{l + 1},\ldots,a_{r}\).

Dữ liệu vào:

• Dòng đầu ghi 2 số nguyên dương \(n,\ q\) trong đó \(n\) là số lượng phần tử của dãy số \(A\) và \(q\) là số lượng truy vấn \((1 \leq n \leq 10^{6};1 \leq q \leq 10^{6})\);

• Dòng thứ hai ghi \(n\) số nguyên \(a_{1},a_{2},\ldots a_{n}\) \(( - 10^{7} \leq a_{i} \leq 10^{7};i = 1,2,\ldots,n)\);

• \(q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(l,\ r\ (1 \leq l \leq r \leq n)\);

Kết quả: Ghi \(q\) dòng, mỗi dòng ghi kết quả tìm được tương ứng một cặp chỉ số \(l,\ r\) trong tệp dữ liệu vào.

Ví dụ:

Giới hạn:

• Có 40% test với \(q = 1;1 \leq n \leq 10^{3}\);

• Có 30% test với \(q = 1;1 \leq n \leq 10^{6};1 \leq a_{i} \leq 10^{6};i = 1,2,\ldots,n\);

• Có 30% test không có ràng buộc gì thêm.