問題文

$X_0=seed$
$X_n=1+(X_{n-1}^2+X_{n-1}\times 12345)\mathrm{\%}100000009(1\le n\le N)$

ただし $\mathrm{\%}$ は剰余演算とする

上の定義から作られる $N+1$ 個の要素を持つ数列 $X$ の中から $K$ 個数字を選びそれらを掛け合わせ $T$ とおく。
$T$ を $B$ 進数に変換した時末尾の0の数が最小となる $T$ では末尾の0の数はいくつになるか答えよ。

例えば
$B=18$、$T$ が10進数で「612」なら $T$ は18進数で「1g0」なので末尾の0の数は1個
$B=3$、$T$ が10進数で「36」なら $T$ は3進数で「1100」なので末尾の0の数は2個

入力

$Q$
$see{d}_1$ $N_1$ $K_1$ $B_1$
$see{d}_2$ $N_2$ $K_2$ $B_2$
$\dots$
$see{d}_Q$ $N_Q$ $K_Q$ $B_Q$

• 1行目は $Q(1\le Q\le 1000)$ が与えられる。
• 2行目からの $Q$ 行では $seed(1\le seed\le 100000009)$, $N(1\le N\le 10000)$, $K(1\le K\le N+1)$, $B(2\le B\le 36)$ の組が与えられる。

出力

$Q$ 個の組ごとに末尾の0の数の最小を計算しそれぞれ出力せよ。ただし末尾に改行をつけること。

サンプル

4
98808561 8 6 18
61316635 15 11 4
37650646 100 86 20
98630457 1000 647 2

1
2
6
142