This is the hard version of the problem. The difference between the versions is that in this version, the restriction on the number of 1's remaining in the final string is more strict. You can hack only if you solved all versions of this problem.

You are given a binary string $s_1s_2\ldots s_n$ containing only characters 0 and 1. You may perform $\lfloor\frac{n}{2}\rfloor$ operations. On the $x$-th operation, you may perform the following:

• Select an integer $l$ such that $0 \leq l \leq n-x$. If $l=0$, then nothing is done. Otherwise, the characters $s_l$ and $s_{l+x}$ are both flipped. That is, for each character, if it is $0$, then it is changed to $1$, and vice versa.

Your task is to find a series of operations such that the number of 1's remaining in the binary string is at most $7$. It can be shown that under the constraints of this problem, this is always possible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($3 \leq n \leq 2\cdot 10^6$).

The second line of each test case contains a binary string $s_1s_2\ldots s_n$ ($s_i \in \{0,1\}$).

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

Output

For each test case, output $\lfloor\frac{n}{2}\rfloor$ numbers on a new line: the chosen $l$ for operation $1,2,\ldots,\lfloor\frac{n}{2}\rfloor (0 \leq l_x \leq n-x)$. You should guarantee that after all operations, there are at most $7$ 1 remaining in the string.

If there are multiple solutions, output any.

Note

In the fourth test case:

• Initially, $s=$111111111. Since $n=9$, we perform $\lfloor\frac{9}{2}\rfloor=4$ operations.
• The first operation has $l=6$. Therefore, characters $6$ and $6+1=7$ are flipped. Now, $s=$111110011.
• The second operation has $l=2$. Therefore, characters $2$ and $2+2=4$ are flipped. Now, $s=$101010011.
• The third operation has $l=0$. Therefore, nothing is done.
• The fourth operation has $l=2$. Therefore, characters $2$ and $2+4=6$ are flipped. Now, $s=$111011011.
• Since the final string has $7$ 1's and $7 \leq 7$, this solution is correct.