Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Recently, Chef has moved to an evil land. In this land, there is only one bank, which offers $N$ savings plans (numbered $1$ through $N$).

Initially, Chef has $1$ coin in his account. He may choose bank plans for as long as he wishes, in any order; each plan may be chosen any number of times. For each valid $i$, whenever Chef chooses the $i$-th savings plan, the number of coins in his bank account gets multiplied by the interest factor $P_{i}$ of this plan (whenever he chooses this plan again, the number of coins is multiplied by $P_{i}$ again).

Since the bank in the evil land is evil, it always stores the number of coins in each account modulo $M$. Strangely, $M$ is a prime number.

Chef knows that he will win the lottery if the number of coins in his bank account becomes exactly $F$. The bank does not want Chef to win, so it decided to remove some of the $N$ savings plans.

You are the head of the evil bank. Therefore, you need to remove some (possibly none or all) plans in such a way that Chef cannot win the lottery. Find the minimum number of plans you must remove.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $M$ and $F$.
The second line contains $N$ space-separated integers $P_{1}, P_{2}, \ldots, P_{N}$.

------ Output ------
For each test case, print a single line containing one integer — the minimum number of plans to remove.

------ Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{4}$
$1 ≤ M ≤ 2 \cdot 10^{5}$
$M$ is a prime number
$0 ≤ F < M$
$0 ≤ P_{i} < M$ for each valid $i$
$F \neq 1$

----- Sample Input 1 ------
4
2 5 3
2 4
2 3 2
1 2
7 7 0
4 1 3 2 0 6 5
10 11 2
9 1 10 4 5 8 2 3 6 0
----- Sample Output 1 ------
1
1
1
4
----- explanation 1 ------
Example case 1: Chef succeeds when he has $3$ coins in his bank account. He can achieve that by choosing plan $1$ and then plan $2$, since he would get $(2 \cdot 4) \% 5 = 3$ coins.

It is enough to delete plan $1$. Then, Chef cannot get $3$ coins, since he can only multiply the number of coins in his account by $4$.

Example case 3: Strangely, Chef succeeds when he has no coins in his bank account. The only way to achieve that is multiplying by $0$, so it is enough to delete plan $5$.

见题面

见题面