Description

你是某联盟的领导人，现在即将进行一场大清洗。具体地，有 $n$ 个官员，有人同意你的意见，有人不同意你的意见。我们将他们的同意与否的信息记作 01 串 $s$.

每次操作，你可以让行刑队走到三个人面前，他们就会自愿改变自己的意见。具体地，你可以选择三个不同数 $i,j,k\,(i< j< k)$，并将 $s_i,s_j,s_k$ 的值分别反转（是 01 反转，不是把顺序反过来的翻转）。由于你希望行刑队队形整齐，必须有 $j-i=k-j$.

你希望最终让所有人都同意你，即让最终的 01 串全为 1.

由于你嫌麻烦，最多仅能操作 $12345$ 次。

若无法完成，输出 $-1$.

Format

Input

第一行一个正整数 $T\,(1\leq T\leq 100)$ 表示数据组数。

对于每组数据，仅一行一个 01 串 $s$，记长度为 $n$，有 $1\leq n \leq 37000$.

数据保证对于所有 $n$ 的和有 $1\leq\sum n\leq 10^6$.

Output

对于每组数据，若无解，输出一行一个数 $-1$.

否则先输出一行一个整数 $m$ 表示你的操作次数。

随后 $m$ 行每行三个数 $i,j,k$ 表示一次操作。

Samples

2
0110
1010

2
1 2 3
2 3 4
-1

Limitation

1s, 256MiB.