QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB
[0]

# 9705. Multiply

Statistics

Alduhmellah and Behlah both like large numbers, lots of numbers and lots of large numbers. They also like to do calculations on those numbers.

One day, Alduhmellah wrote down N positive integers a1,a2,,aN. He decided to make them large by applying factorial to each number, so the numbers became a1!,a2!,,aN!. Finally, he multiplied all N numbers to get a super-large number Z=a1!×a2!××aN!.

A few days later, Behlah met Alduhmellah, and Behlah told Alduhmellah that he came up with another two numbers X,Y. Thus, they started to repeatedly multiply X to Z, generating a sequence bi=Z×Xi, to find out the largest value of i such that bi is a factor of Y!.

You, being a friend with Alduhmellah and Behlah, realized that it is such a time-wasting process. Thus, to save time, you decided to write a program to calculate the answer.

Input

The first line contains one positive integer T (T8) --- the number of tests.

The description of each test contains two lines: the first line contains three positive integers N,X,Y (N105;2X,Y1018), and the second line contains N positive integers a1,a2,aN (ai1018;a1+a2++aN<Y). Their meanings are explained above.

Output

For each test, output an integer in one line, representing the largest value of i such that bi is a factor of Y!.

Sample Input

2
3 10 10
2 3 4
2 2 10
1 1

Sample Output

2
8