A Hydra with $N$ heads has appeared. The $i$-th head initially has $H_i$ health points.

You may perform attacks any number of times, including zero. In each attack, choose one of the following $N + 1$ types:

• Attack $i$ ($1 \le i \le N$): Decrease the health points of the $i$-th head by $X$.
• Attack $N + 1$: Decrease the health points of every head by $Y$.

Find the minimum number of attacks required to make the health points of every head at most $0$.

Input

The input contains one or more test cases. The first line of the input contains an integer $T$ ($1 \le T \le 100$), which is the number of test cases. The descriptions of the $T$ test cases follow, each in the following format.

$$ \begin{aligned} &N\ X\ Y \\ &H_1\ H_2\ \ldots\ H_N \end{aligned} $$

For each test case, the first line contains three integers $N$, $X$, and $Y$ ($1 \le N \le 3 \times 10^5$, $1 \le X, Y \le 10^{18}$), representing the number of heads, the damage dealt by Attack $i$ ($1 \le i \le N$), and the damage dealt by Attack $N + 1$, respectively.

The second line contains $N$ integers $H_1, H_2, \ldots, H_N$ ($1 \le H_i \le 10^{18}$), where $H_i$ represents the initial health points of the $i$-th head.

The sum of $N$ over all test cases does not exceed $3 \times 10^5$.

Output

For each test case, print a single integer representing the minimum number of attacks required to make the health points of every head at most $0$.

Example

Input 1

2
3 5 2
12 6 17
1 998244353 1000000007
1000000007

Output 1

7
1