Hydra með $N$ höfuð hefur birst. Höfuð númer $i$ hefur í upphafi $H_i$ lífsgildi.

Þú mátt framkvæma árásir hversu oft sem er, þar á meðal núll sinnum. Í hverri árás skaltu velja eina af eftirfarandi $N + 1$ tegundum:

• Árás $i$ ($1 \le i \le N$): Minnkaðu lífsgildi höfuðs númer $i$ um $X$.
• Árás $N + 1$: Minnkaðu lífsgildi hvers höfuðs um $Y$.

Finndu lágmarksfjölda árása sem þarf til að gera lífsgildi hvers höfuðs í mesta lagi $0$.

Inntak

Inntakið inniheldur eitt eða fleiri prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 100$), sem er fjöldi prófunartilvika. Lýsingar á prófunartilvikunum $T$ fylgja á eftir, hver á eftirfarandi sniði.

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

Fyrir hvert prófunartilvik inniheldur fyrsta línan þrjár heiltölur $N$, $X$ og $Y$ ($1 \le N \le 3 \times 10^5$, $1 \le X, Y \le 10^{18}$), sem tákna fjölda höfða, skaðann sem Árás $i$ ($1 \le i \le N$) veldur og skaðann sem Árás $N + 1$ veldur, í þessari röð.

Önnur línan inniheldur $N$ heiltölur $H_1, H_2, \ldots, H_N$ ($1 \le H_i \le 10^{18}$), þar sem $H_i$ táknar upphaflegt lífsgildi höfuðs númer $i$.

Summa $N$ yfir öll prófunartilvik fer ekki yfir $3 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta eina heiltölu sem táknar lágmarksfjölda árása sem þarf til að gera lífsgildi hvers höfuðs í mesta lagi $0$.

Dæmi

Inntak 1

2
3 5 2
12 6 17
1 998244353 1000000007
1000000007

Úttak 1

7
1