A. Antiprefix Function
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let the antiprefix function of the string $$$s$$$ be an array $$$[q_{1},q_{2},...,q_{n}]$$$, where $$$q_{i}$$$ is the greatest integer $$$j \in [0,i-1]$$$ such that $$$s[1..j]$$$ differs from $$$s[i-j+1..i]$$$ in every position.

For example, for the string $$$011001$$$, its antiprefix function is $$$[0,1,1,2,3,4]$$$.

You are given a binary string $$$s$$$ of length $$$n$$$, find its antiprefix function.

Input

The first line contains one integer $$$t$$$ $$$( 1 \le t \le 10^4)$$$ — the number of test cases.

The first line of each test case contains one integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the length of the binary string $$$s$$$.

The second line of each test case contains a binary string consisting of $$$n$$$ characters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2.10^5$$$

Output

For each test case, output $$$n$$$ integers : the antiprefix function of the string $$$s$$$.

Example
Input
2
6
011001
9
010101010
Output
0 1 1 2 3 4 
0 1 2 3 4 5 6 7 8