テーブルの上に $n$ 堆の積木が整列しており、第 $i$ 堆 ($1 \le i \le n$) の初期の積木数は $a_i$ です。

小Tと小Sは、それぞれ網目サイズが $p, q$ である2つの魔法の篩（ふるい）を提供しました。これらを用いると、覆われた範囲の積木堆を対応する法で割った余りに置き換えることで、積木をまとめて消去できます。自然に展開したとき、これらの篩はちょうど $k$ 堆分の幅を跨ぎます。これらは特殊な弾性を持ち、より広い範囲を覆うために両端へ自由に引き伸ばすことができますが、内側に圧縮して縮めることはできません。魔法の篩の使用方法は以下の通りです。

• 長さが少なくとも $k$ である連続する積木の区間 $[l, r]$ を選択し、篩を敷きます。
• 2つの魔法の篩から一方を選択します。すなわち、$m \in \{p, q\}$ を選択します。
• 区間 $[l, r]$ 内の各積木堆について、その数を $m$ で割った余りに置き換えます。すなわち、$a_i \leftarrow a_i \pmod m$ とします。

このゲームに参加する以上、平凡な成績では満足できないでしょう。ランキングで上位に入るために、魔法の篩を任意の回数繰り返し使用することで、最終的にテーブル上に残る積木の総数（すなわち $\sum_{i=1}^n a_i$）を最小でいくつまで減らせるかを知りたいと考えています。

入力

各テストケースには複数のテストデータが含まれます。入力の最初の行には正整数 $T$ ($1 \le T \le 10^3$) が含まれ、データセットの数を示します。各テストデータについて：

• 最初の行には4つの正整数 $n, k, p, q$ ($1 \le k \le n \le 10^5, 1 \le p < q \le 10^9$) が含まれ、それぞれ積木の堆数、篩が自然に展開したときに跨ぐ積木堆の数、および2つの魔法の篩の網目サイズを表します。
• 2行目には $n$ 個の正整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) が含まれ、それぞれ各積木堆の初期の数を表します。

すべてのテストデータにおいて、$n$ の総和は $10^5$ を超えないことが保証されます。

出力

各テストデータについて、テーブル上に残る積木の総数の最小値を表す非負整数を1行に出力してください。

入出力例

入力 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

出力 1

1
11
3
0
4
569

注記

2番目のテストデータについて、テーブル上の積木の総数を最小値 11 にする操作手順は以下の通りです。

• 区間 $[1, 4]$ を選択し、網目サイズ 10 の魔法の篩を使用すると、残りの積木数は $[1, 1, 9]$ になります。

3番目のテストデータについて、テーブル上の積木の総数を最小値 3 にする操作手順は以下の通りです。

• 区間 $[2, 4]$ を選択し、網目サイズ 4 の魔法の篩を使用すると、残りの積木数は $[1, 2, 3, 0]$ になります。
• 区間 $[1, 3]$ を選択し、網目サイズ 3 の魔法の篩を使用すると、残りの積木数は $[1, 2, 0, 0]$ になります。