This problem is a programming version of Problem 214 from projecteuler.net
Let be Euler's totient function, i.e. for a natural number , is the number of , for which .
By iterating , each positive integer generates a decreasing chain of numbers ending in .
E.g. if we start with the sequence is generated.
For an integer , denote the length of its chain. For example, and .
Let be the sequence of prime numbers (, , ...), and consider two positive integers and . We define the set as:
You will be given and , how many integers satisfy . Print your answer modulo .
Input Format
The first line of each test file contains three space-separated integers , (as described above) and which is the number of queries.
Each of the next lines contains a value of .
Constraints
- .
- .
- .
Output Format
Print the answer to each query in a new line.
Sample Input
3 2 5
2
3
1
4
7
Sample Output
1
3
1
5
4
Explanation
E.g. (last query), the answer is 4.