$N$-päinen Hydra on ilmestynyt. Sen $i$-nnellä päällä on aluksi $H_i$ elämäpistettä.

Voit tehdä hyökkäyksiä mielivaltaisen määrän kertoja, myös nolla kertaa. Valitse jokaisella hyökkäyksellä yksi seuraavista $N + 1$ tyypistä:

• Hyökkäys $i$ ($1 \le i \le N$): Vähennä $i$-nnen pään elämäpisteitä määrällä $X$.
• Hyökkäys $N + 1$: Vähennä jokaisen pään elämäpisteitä määrällä $Y$.

Etsi pienin mahdollinen hyökkäysten määrä, jolla jokaisen pään elämäpisteet saadaan korkeintaan arvoon $0$.

Syöte

Syöte sisältää yhden tai useamman testitapauksen. Syötteen ensimmäisellä rivillä on kokonaisluku $T$ ($1 \le T \le 100$), joka on testitapausten lukumäärä. Tämän jälkeen seuraavat $T$ testitapauksen kuvaukset, joista jokainen on seuraavassa muodossa.

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

Jokaisen testitapauksen ensimmäisellä rivillä on kolme kokonaislukua $N$, $X$ ja $Y$ ($1 \le N \le 3 \times 10^5$, $1 \le X, Y \le 10^{18}$), jotka ilmaisevat päiden lukumäärän, hyökkäyksen $i$ ($1 \le i \le N$) tekemän vahingon sekä hyökkäyksen $N + 1$ tekemän vahingon tässä järjestyksessä.

Toisella rivillä on $N$ kokonaislukua $H_1, H_2, \ldots, H_N$ ($1 \le H_i \le 10^{18}$), missä $H_i$ ilmaisee $i$-nnen pään alkuperäiset elämäpisteet.

Lukujen $N$ summa yli kaikkien testitapausten ei ylitä arvoa $3 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi kokonaisluku, joka ilmaisee pienimmän mahdollisen hyökkäysten määrän, jolla jokaisen pään elämäpisteet saadaan korkeintaan arvoon $0$.

Esimerkit

Syöte 1

2
3 5 2
12 6 17
1 998244353 1000000007
1000000007

Tuloste 1

7
1