Ben is given a set S of N integers and two numbers M, Z. Initially M is 1. He can choose an element X from the set and multiply M with X mod Z (i.e. he can make M = (M * X) % Z). Ben is also given a number F. The goal is to make M = F, by doing the above operation any number of times.He may choose the same X as many times he wants.
But Chris doesn’t want him to complete the task and go running with him instead. So he decides to remove some numbers from the set S. What is the minimum number of elements he should remove from the set S so that Ben can’t fulfil his task.
First line of input contains an integer T denoting the numebr of test cases.
The first line of each test case contains 3 integers N, Z and F respectively
The next line contains N space separated integers denoting the numbers in the set, all the elements of the set S are distinct.
Print the answer corresponding to each test case in a seperate line
1 ≤ T ≤ 50
1 ≤ N ≤ 104
1 ≤ Z ≤ 2*105 (Z is a prime number)
0 ≤ F ≤ Z
0 ≤ X ≤ Z (Elements in the set)
In the first test case Ben succeeds when M = 3.
He can obtain M = 3, by doing the following steps -
Initially M = 1.
Multiply 2 once and multiply 4 once M =(2*4) mod 5 i.e. M = 3.
So Chris deletes 2.
Chris don’t have to delete 4 as Ben can’t reach 3 by multiplying any number of 4’s.
In the the third test case Ben succeeds when M =0;
The only way to make M = 0 by multiplying with 0, Chris deletes 0 from the set.