- All Contests
- ProjectEuler+
- Project Euler #214: Totient Chains

# Project Euler #214: Totient Chains

# Project Euler #214: Totient Chains

_{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.