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 (T≤8) --- the number of tests.
The description of each test contains two lines: the first line contains three positive integers N,X,Y (N≤105;2≤X,Y≤1018), and the second line contains N positive integers a1,a2,⋯aN (ai≤1018;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