B. 0100101
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a 01-string $$$s$$$ of length $$$n$$$ and a positive integer $$$k$$$.

Your task is to construct a sequence $$$a$$$ of positive integers satisfying the following conditions:

  • of length $$$n+1$$$;

  • $$$1 \leq a_i \leq 100$$$;

  • for any integer $$$i$$$ between $$$1$$$ and $$$n$$$, $$$\frac{a_i}{a_{i+1}}$$$ has a finite representation in base $$$k$$$ if and only if $$$s_i=1$$$$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$For example, in base $$$10$$$, $$$\frac{1}{8}=0.125$$$ has a finite representation, but $$$\frac{1}{3}=0.333\ldots$$$ has an infinite representation.

Input

Each test file consists of multiple test cases. The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$ denoting the number of test cases.

For each test case, the first line contains two integers $$$n,k$$$ $$$(1 \leq n \leq 2 \times 10^5, 2 \leq k \leq 10^{18})$$$.

The second line contains a 01-string $$$s$$$ of length $$$n$$$ $$$(s_i \in \{0,1\})$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single line containing $$$n+1$$$ positive integers $$$a_i$$$ $$$(1 \leq a_i \leq 100)$$$, representing the sequence $$$a$$$ you constructed.

Example
Input
2
3 10
101
7 2
0100101
Output
2 1 3 6
1 3 4 5 7 8 9 9
Note

For the first test case of the sample:

$$$\frac{a_1}{a_2} = 2,\frac{a_3}{a_4}= \frac{1}{2}$$$ are both integers or finite decimals in base $$$10$$$;

$$$\frac{a_2}{a_3} = \frac{1}{3}$$$ is an infinite decimal in base $$$10$$$.