Cho dãy số có \(N\) phần tử \((2 \le A_i \le 10^7)\) và \(Q\) truy vấn (mỗi truy vấn gồm \(L\) và \(R\)). Hãy đếm số lượng số nguyên tố có trong đoạn \([L,R]\).

Ràng buộc:

• \(10 \le N, Q \le 10^5\)
• \(0 \le L \le R \le N\)

Dữ liệu vào:

• Dòng thứ nhất: có 2 số \(N\) và \(Q\)
• Q Dòng tiếp theo: mỗi dòng chứa 2 số \(L\) và \(R\)

Dữ liệu ra:

• Q dòng: mỗi dòng là số lượng số nguyên tố có trong đoạn \(L, R\)

Lưu ý: vị trí bắt đầu từ \(0\)

Input

10 1
2 3 4 5 6 7 8 9 10 11
0 1

Output

2