Problem Statement

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

Here, \(\%\) denotes the modulo operation.

From the sequence \(X\) with \(N+1\) elements built by the definition above, choose \(K\) numbers and multiply them together; call the product \(T\).
When \(T\) is converted to base \(B\), find the number of trailing 0s for the \(T\) that minimizes the number of trailing 0s.

For example,
if \(B=18\) and \(T\) is "612" in base 10, then \(T\) is "1g0" in base 18, so the number of trailing 0s is 1.
If \(B=3\) and \(T\) is "36" in base 10, then \(T\) is "1100" in base 3, so the number of trailing 0s is 2.

Input

\(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}\)

• The first line contains \(Q(1 \leq Q \leq 1000)\).
• Each of the \(Q\) lines starting from the second line contains a tuple of \(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)\).

Output

For each of the \(Q\) tuples, compute the minimum number of trailing 0s and output it. Print a newline at the end.

Sample

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

1
2
6
142