Read problems statements in Mandarin Chinese and Russian as well.
You are given a function f which is defined as :

Your task is to find the value of

where M is given in input.

------ Input Format ------

First line contains T, the number of test cases.

First line of each test case contain 3 space separated integers N, M and Q.

Next Q line follows, each line contain r.

------ Output Format ------

For each test case, output Q lines, each line containing the required answer.

------ Constraints ------

2 ≤ N ≤ 10^{6}

1 ≤ M ≤ 10^{9}

2 ≤ Sum of N over all test cases ≤ 10^{6}

1 ≤ Sum of Q over all test cases ≤ 2*10^{5}

1 ≤ T ≤ 10^{5}

1 < r < N

Sample Input
2
5 114 1
2
50 3874 3
31
17
21

Sample Output
72
3718
624
1144

Explanation for first test case
f[1] = 1

f[2] = 2

f[3] = 1*2^{2} * 3 = 12

f[4] =12^{3}3^{2}4 = 89*4 = 288

f[5] = 12^{4}3^{3}4^{2}5 =34560

value of f[5] / (f[2]*f[3]) = 1440 and 1440 %114 is 72

见题面

见题面