問題文

\(X_{0} = seed\)
\(X_{n} = 1 + (X_{n-1} ^ 2 + X_{n-1} \times 12345)\ \%\ 100000009\ \ \ \ (1 \leq n \leq N)\)

ただし \(\%\) は剰余演算とする

上の定義から作られる \(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\)
\(seed_{1}\) \(N_{1}\) \(K_{1}\) \(B_{1}\)
\(seed_{2}\) \(N_{2}\) \(K_{2}\) \(B_{2}\)
\(\ldots\)
\(seed_{Q}\) \(N_{Q}\) \(K_{Q}\) \(B_{Q}\)

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

出力

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

サンプル

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

1
2
6
142