J. Zaghloul and the spies
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

During the 1919 revolution, Zaghloul noticed that there were spies hiding among the Egyptians. He tasked Zeyad with finding them to save Egypt.

There are $$$n$$$ people standing in a row. The $$$i$$$-th person holds an integer $$$a_i$$$. A person is considered a spy if the bitwise XOR sum of all divisors of their number $$$a_i$$$ is divisible by $$$k$$$.

You need to answer $$$q$$$ queries. For each query, find the number of spies in the range $$$[l, r]$$$.

Input

The first line contains three integers $$$n$$$, $$$q$$$, and $$$k$$$ ($$$1 \le n, q, k \le 10^6$$$) — the number of people, the number of queries, and the divisor check value.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the numbers held by the people.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the range of the query.

Output

For each query, find the number of spies in the range.

Example
Input
5 4 2
2 3 4 5 6
1 5
1 3
1 1
2 4
Output
3
1
0
2