Smudged Cat Strings

Time limit: 2000 msMemory limit: 256 MB

Gats the cat found a string of beads. The bead at position $i$ has the letter $S_i$ .

Gats wants to tie a loop by overlapping some beads from the left end with the same number of beads from the right end. A small smudge is allowed.

For a length $\ell$ with $1 \le \ell < N$ , Gats compares the first $\ell$ symbols, $S_1 S_2 \ldots S_\ell$ , with the last $\ell$ symbols, $S_{N-\ell+1} S_{N-\ell+2} \ldots S_N$ , in the same left-to-right order.

The length $\ell$ is called a smudged loop length if the two compared strings differ in at most one position, that is,

\left|\left\{j \mid 1 \le j \le \ell,\ S_j \ne S_{N-\ell+j}\right\}\right| \le 1.

For each string, list all smudged loop lengths.

Input

The first line contains an integer $T$ ( $1 \le T \le 2 \times 10^4$ ), the number of strings.

For each test case, the first line contains an integer $N$ (), the length of .

Output

For each test case, print two lines.

The first line contains an integer $K$ , the number of smudged loop lengths.

The second line contains $K$ integers in strictly increasing order: all valid values of $\ell$ . If $K = 0$ , the second line must be empty.

Samples

Sample 1

Input

3
5
ababa
6
catcot
1
m

Output

For the first string, the valid values are $\ell = 1$ and $\ell = 3$ .

For the second string, the valid values are $\ell = 1$ and $\ell = 3$ ; when , the two compared ends differ in only one position.

Smudged Cat Strings

Input

Output

Samples

Sample 1

Submit

Submissions