Little C has a digit string $S_{1\sim n}$ of length $n$. Here, $S_i$ denotes the $i$-th character of the string $S$.

Little C defines a digit string to be mythical if and only if every non-empty substring of it corresponds to a decimal integer that is not divisible by $9$.

For a digit string $A_{1\sim m}$, a non-empty substring means a consecutive segment of the form $A_lA_{l+1}\cdots A_r$, where $1\le l\le r\le m$. The number represented by a substring may have leading zeros.

Now, Little C wants to choose a subsequence $T$ from $S$ such that $T$ is mythical, and under this condition maximize $|T|$.

A digit string $T$ is a subsequence of $S$ if and only if there exist indices $1\le x_1

You need to output one longest subsequence that satisfies the condition. If there are multiple valid solutions, output any one of them.

Input

The first line contains an integer $t$ ($1\le t\le 1000$), the number of test cases.

For each test case:

The first line contains an integer $n$ ($n \ge 1,\sum n \le 5\times 10^6$), the length of the digit string $S$.

The second line contains a digit string $S$ of length $n$, guaranteed to consist only of characters from 0 to 9.

Output

For each test case, output one line.

Suppose the length of the longest subsequence you choose is $k$ ($0\le k\le n$), and the corresponding indices are $x_1,x_2,\ldots,x_k$. Then the line should output:

$$ k\ x_1\ x_2\ \cdots\ x_k $$

Numbers should be separated by a single space.

You must ensure that $1\le x_1

If $k=0$, then output only the integer $0$ on that line.

If there are multiple optimal valid solutions, output any one of them.

Examples

Input 1

3
4
0522
6
831426
9
998244353

Output 1

2 3 4
5 2 3 4 5 6
5 4 5 6 7 9

Note

Please make sure the output format is correct; otherwise, we cannot guarantee that the judge will return a normal evaluation result.