Na stole znajduje się $n$ stosów klocków, przy czym początkowa liczba klocków w $i$-tym stosie ($1 \le i \le n$) wynosi $a_i$.

Mały T i mały S udostępnili dwa magiczne sita o rozmiarach oczek odpowiednio $p$ oraz $q$, które pozwalają na masowe usuwanie klocków poprzez operację modulo. W stanie naturalnego rozłożenia oba sita obejmują dokładnie $k$ stosów klocków. Posiadają one specjalną elastyczność, dzięki której można je dowolnie rozciągać w obie strony, aby pokryły szerszy zakres, jednak nie można ich zwężać. Sposób użycia magicznego sita jest następujący:

• Wybierz przedział ciągłych stosów klocków $[l, r]$ o długości co najmniej $k$ i nałóż na niego sito;
• Wybierz jedno z dwóch magicznych sit, czyli wybierz $m \in \{p, q\}$;
• Dla każdego stosu klocków w przedziale $[l, r]$ zastąp jego liczbę klocków resztą z dzielenia przez $m$, czyli wykonaj $a_i \leftarrow a_i \pmod m$.

Chcesz wiedzieć, jaka jest minimalna łączna liczba klocków, która może pozostać na stole (czyli $\sum_{i=1}^n a_i$) po wykonaniu dowolnej liczby operacji z użyciem magicznych sit.

Wejście

Każdy zestaw testowy zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^3$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

• Pierwsza linia zawiera cztery liczby całkowite $n, k, p, q$ ($1 \le k \le n \le 10^5$, $1 \le p < q \le 10^9$), oznaczające odpowiednio liczbę stosów klocków, liczbę stosów obejmowanych przez sito w stanie naturalnym oraz rozmiary oczek dwóch magicznych sit.
• Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), oznaczających początkową liczbę klocków w każdym stosie.

Suma $n$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w jednej linii nieujemną liczbę całkowitą oznaczającą minimalną łączną liczbę klocków pozostałych na stole.

Przykład

Wejście 1

6
1 1 3 4
2 0 26
3 2 10 20
3 1 41 59
4 3 3 4
1 2 3 4
6 4 9 20
18 27 180 9 45 99
7 4 3 5
6 7 14 12 100 78 4
9 4 244 353
9982 4435 3998 2443 5399 8244 3539 9824 4353

Wyjście 1

1
11
3
0
4
569

Uwagi

Dla drugiego przypadku testowego, przykładowy sposób osiągnięcia minimalnej sumy 11:

• Wybierz przedział $[1, 4]$ i użyj magicznego sita o rozmiarze oczek 10, liczba klocków zmienia się na $[1, 1, 9]$.

Dla trzeciego przypadku testowego, przykładowy sposób osiągnięcia minimalnej sumy 3:

• Wybierz przedział $[2, 4]$ i użyj magicznego sita o rozmiarze oczek 4, liczba klocków zmienia się na $[1, 2, 3, 0]$;
• Wybierz przedział $[1, 3]$ i użyj magicznego sita o rozmiarze oczek 3, liczba klocków zmienia się na $[1, 2, 0, 0]$.