È apparsa un'Idra con $N$ teste. La $i$-esima testa ha inizialmente $H_i$ punti vita.

Puoi effettuare attacchi un qualsiasi numero di volte, incluso zero. In ogni attacco, scegli uno dei seguenti $N + 1$ tipi:

• Attacco $i$ ($1 \le i \le N$): Riduci i punti vita della $i$-esima testa di $X$.
• Attacco $N + 1$: Riduci i punti vita di ogni testa di $Y$.

Trova il numero minimo di attacchi necessari per rendere i punti vita di ogni testa al più $0$.

Input

L'input contiene uno o più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 100$), che rappresenta il numero di casi di test. Seguono le descrizioni dei $T$ casi di test, ciascuna nel formato seguente.

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

Per ogni caso di test, la prima riga contiene tre interi $N$, $X$ e $Y$ ($1 \le N \le 3 \times 10^5$, $1 \le X, Y \le 10^{18}$), che rappresentano rispettivamente il numero di teste, il danno inflitto dall'Attacco $i$ ($1 \le i \le N$) e il danno inflitto dall'Attacco $N + 1$.

La seconda riga contiene $N$ interi $H_1, H_2, \ldots, H_N$ ($1 \le H_i \le 10^{18}$), dove $H_i$ rappresenta i punti vita iniziali della $i$-esima testa.

La somma di $N$ su tutti i casi di test non supera $3 \times 10^5$.

Output

Per ogni caso di test, stampa un singolo intero che rappresenta il numero minimo di attacchi necessari per rendere i punti vita di ogni testa al più $0$.

Esempi

Input 1

2
3 5 2
12 6 17
1 998244353 1000000007
1000000007

Output 1

7
1