Cho số \(N\) và dãy \(A\) (\(A1, A2,...AN\)). Để 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:
\(A[i] = (P*i)\) % \(M + Q\) ,(\(1 \le i \le N\))
Có \(T\) câu hỏi dạng \(U, V\) (\(U \le V\)) yêu cầu cho biết trong đoạn \(A[U], A[U+1],...A[V]\) có bao nhiêu số nguyên tố

Thông số đầu vào

Dòng 1: Chứa hai số nguyên dương \(N, T\) (\(N \le 10^6, T \le 10^6\))
Dòng 2: Dòng 2 chứa ba số nguyên dương \(P, Q, M\) xác định dãy A (\(P, Q, M \le 10^6\))
\(T\) dòng tiếp theo, dòng thứ \(i\) chứa 2 số \(U, V\) (\(U, V \le N\))

Thông số đầu ra

Ghi trên T dòng, mỗi dòng ghi câu trả lời cho từng câu hỏi

Ví dụ đầu vào

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

Ví dụ đầu ra

3
2
2
0

Giải thích

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

Ràng buộc

20% số test có \(N \le 100, T \le 100\)
20% số test có \(N \le 1\,000, T \le 1\,000\)
20% số test có \(N \le 10\,000, T \le 10\,000\)
20% số test có \(N \le 100\,000, T \le 100\,000\)
20% số test còn lại không ràng buộc gì thêm