Alduhmellah 和 Behlah 都喜欢大数，喜欢很多数字，也喜欢很多大数。他们还喜欢对这些数字进行计算。

有一天，Alduhmellah 写下了 $N$ 个正整数 $a_1, a_2, \cdots, a_N$。他决定通过对每个数求阶乘来使它们变大，于是这些数变成了 $a_1!, a_2!, \cdots, a_N!$。最后，他将这 $N$ 个数相乘，得到一个超大的数 $Z=a_1!\times a_2!\times\cdots\times a_N!$。

几天后，Behlah 遇到了 Alduhmellah，Behlah 告诉 Alduhmellah 他又想出了另外两个数 $X$ 和 $Y$。于是，他们开始不断地将 $X$ 乘到 $Z$ 上，生成一个序列 $b_i=Z\times X^i$，目的是找出最大的 $i$，使得 $b_i$ 是 $Y!$ 的因数。

作为 Alduhmellah 和 Behlah 的朋友，你意识到这是一个非常浪费时间的过程。因此，为了节省时间，你决定编写一个程序来计算这个答案。

第一行包含一个正整数 $T$ ($T\leq 8$)，表示测试数据的组数。

每组测试数据的描述包含两行：第一行包含三个正整数 $N, X, Y$ ($N\leq 10^5; 2\leq X,Y\leq 10^{18}$)，第二行包含 $N$ 个正整数 $a_1, a_2, \cdots, a_N$ ($a_i \leq 10^{18}; a_1+a_2+\cdots+a_N< Y$)。它们的含义如上所述。

对于每组测试数据，输出一行一个整数，表示使得 $b_i$ 是 $Y!$ 的因数的最大 $i$ 值。

样例

输入格式 1

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

输出格式 1

2
8