Cho một mảng số nguyên A gồm N phần tử và một số nguyên k. Hãy viết chương trình xử lý Q truy vấn, mỗi truy vấn yêu cầu đếm số phần tử trong đoạn [L, R] chia hết cho k.

Dữ liệu vào:

• Dòng đầu tiên chứa ba số nguyên N, Q và k (1 ≤ N, Q ≤ 105, 1 ≤ k ≤ 104) – số phần tử của mảng, số truy vấn và số nguyên k.
• Dòng thứ hai chứa N số nguyên A1, A2, ..., AN (-104 ≤ Ai ≤ 104) – các phần tử của mảng.
• Mỗi dòng trong Q dòng tiếp theo chứa hai số nguyên L, R (1 ≤ L ≤ R ≤ N) - chỉ số bắt đầu và kết thúc của đoạn cần đếm số phần tử chia hết cho k.

Dữ liệu ra:

• Với mỗi truy vấn, in ra một số nguyên là số phần tử trong đoạn [L, R] chia hết cho k.

Ví dụ:

Input:
5 3 2
1 2 3 4 5
1 3
2 5
1 5

Output:
1
2
2