405167: GYM101808 G Weird Requirements

It is hard to find teams for students to participate in ACM contests, most students have weird requirements for their team mates. For example, Ziad wants the GCD of all his team mate's ratings on all famous websites to be exactly X and the LCM of his ratings to be exactly Y.

There are N famous competitive programming websites. Ramzi's rating on the i^th website is A_i. Ramzi is very experienced, in one contest, he can change his rating on one website to any other value. What is the minimum number of contests that Ramzi must participate in, so that Ziad accepts him as his team mate?

The first line contains one integer T, the number of test cases.

Each test case starts with one line containing three space-separated integers N, X, and Y, the number of famous websites, the required GCD value, and the required LCM value respectively. (1 ≤ N ≤ 10⁵) (1 ≤ X, Y ≤ 10⁹)

The next line contains N space-separated integers A_i, Ramzi's rating on all websites. (1 ≤ A_i ≤ 10⁹)

For each test case print one line containing one integer, the minimum number of contests Ramzi must participate in so that he can become Ziad's team mate.

If it is impossible for Ziad to accept him as his team mate , print -1.

1
5 1 10
1 5 1 10 10

0

The Greatest Common Divisor (GCD) of an array is the maximum number that divides all integers in the array without remainder.

The Least Common Multiple (LCM) of an array is the minimum positive number that is a multiple of all integers in the array.