Số nguyên tố trong dãy con

Số nguyên dương \(x\) được gọi là số nguyên tố nếu nó chỉ có 2 ước là 1 và chính nó.

Cho một dãy số nguyên \(a\) gồm \(n\) phần tử \(a_1, a_2, \dots, a_n\). Có \(k\) dãy con được lấy từ dãy số nguyên \(a\), mỗi dãy con được xác định bằng cặp số \((d, c)\) (\(d\) là chỉ số đầu và \(c\) là chỉ số cuối của dãy con, \(1 \le d \le c \le n\)). Với mỗi dãy con, đếm xem có bao nhiêu số nguyên tố trong đó.

Input

Dữ liệu vào: Đọc từ tệp DSNT.INP có cấu trúc:

• Dòng đầu ghi hai số nguyên dương \(n\) và \(k\) (\(n, k \le 10^5\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^5\)).
• \(k\) dòng tiếp theo, mỗi dòng ghi một cặp số nguyên dương \(d, c\).

Output

Dữ liệu ra: Ghi vào tệp DSNT.OUT gồm \(k\) dòng, mỗi dòng ghi số lượng số nguyên tố trong dãy con tương ứng.

Example

6 2
2 4 6 8 5 3
2 4
3 6

0
2

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm có \(n \leq 10^3\), \(k \le 10\).
• \(40\%\) số test khác ứng với \(40\%\) số điểm với trường hợp còn lại.