Đề bài
Bạn được cho biết số ~ N ~ (~ N \leq 1000 ~) và dãy ~ A = (a_1, a_2, \dots, a_N) ~. Để tránh việc phải đọc một lượng dữ liệu quá lớn, dãy ~ A ~ sẽ được cho bởi ba số nguyên dương ~ p, q, m ~, trong đó mỗi phần tử ~ a_i ~ được xác định theo công thức:

Có ~ T ~ câu hỏi dạng ~ u, v ~ (~ u \leq v ~) yêu cầu cho biết trong đoạn ~ a_u, a_{u+1}, \dots, a_v ~ có bao nhiêu số nguyên tố?

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ~ N, T ~;
• Dòng thứ hai chứa ba số nguyên ~ p, q, m ~ xác định dãy ~ A ~ (~ p, q, m \leq 10^5 ~);
• ~ T ~ dòng tiếp theo, dòng thứ ~ i ~ chứa hai số ~ u, v ~ dùng để trả lời câu hỏi ~ i ~ là trong đoạn ~ a_u, a_{u+1}, \dots, a_v ~ có bao nhiêu số nguyên tố.

Dữ liệu ra:

• Ghi trên ~ T ~ dòng, dòng thứ ~ i ~ ghi câu trả lời cho câu hỏi ~ i ~.

Ví dụ:

Dữ liệu vào:

5 4  
2 1 9  
1 3  
2 4  
3 5  
4 4  

Dữ liệu ra:

3  
2  
2  
0  

Giải thích:

• Dãy ~ A = (3, 5, 7, 9, 2) ~:
  
  • Đoạn ~ [1, 3] ~ có ~ (3, 5, 7) ~ có 3 số nguyên tố;
  • Đoạn ~ [2, 4] ~ có ~ (5, 7, 9) ~ có 2 số nguyên tố;
  • Đoạn ~ [3, 5] ~ có ~ (7, 9, 2) ~ có 2 số nguyên tố;
  • Đoạn ~ [4, 4] ~ có ~ (9) ~ có 0 số nguyên tố.

Giới hạn:

• 40% số điểm ứng với các test có ~ N \leq 1000, T = 1 ~;
• 40% số điểm ứng với các test có ~ N \leq 1000, T \leq 1000 ~;
• 20% số điểm ứng với các test có ~ N \leq 1000, T \leq 10000 ~.