33OJ
登录 注册

#P17735. [ICPC 2019 Xuzhou R] Multiply

[ICPC 2019 Xuzhou R] Multiply

Problem Description

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 NN positive integers a1,a2,⋯ ,aNa_1, a_2,\cdots, a_N. He decided to make them large by applying factorial to each number, so the numbers became a1!,a2!,⋯ ,aN!a_1!, a_2!,\cdots, a_N!. Finally, he multiplied all NN numbers to get a super-large number Z=a1!×a2!×⋯×aN!Z=a_1!\times a_2!\times\cdots\times a_N!.

A few days later, Behlah met Alduhmellah, and Behlah told Alduhmellah that he came up with another two numbers X,YX,Y. Thus, they started to repeatedly multiply XX to ZZ, generating a sequence bi=Z×Xib_i=Z\times X^i, to find out the largest value of ii such that bib_i is a factor of Y!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 Format

The first line contains one positive integer TT (T≤8T\leq 8) --- the number of tests.

The description of each test contains two lines: the first line contains three positive integers N,X,YN, X, Y (N≤105;2≤X,Y≤1018N\leq 10^5; 2\leq X,Y\leq 10^{18}), and the second line contains NN positive integers a1,a2,⋯aNa_1, a_2,\cdots a_N (ai≤1018;a1+a2+⋯+aN<Ya_i \leq 10^{18}; a_1+a_2+\cdots+a_N<Y). Their meanings are explained above.

Output Format

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

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