三进制字符串是由数字 0、1 或 2 组成的序列。

Chiaki 有一个非空三进制字符串 $s$。初始时，字符按非递减顺序排列（所有的 0 出现在所有的 1 之前，所有的 1 出现在所有的 2 之前）。Chiaki 想要重新排列这些字符，使得没有两个相邻的字符具有相同的值。为此，她将使用以下操作：选择两个整数 $l$ 和 $r$ ($l \le r$)，取出从位置 $l$ 到位置 $r$（包含两端）的字符，并将它们移动到字符串的末尾。

Chiaki 想知道所需的最少操作次数。

输入格式

输入包含多组测试数据。第一行是一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个三进制字符串 $s$ ($1 \le |s| \le 10^6$)。

保证所有 $|s|$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，如果 Chiaki 无法通过上述操作重新排列字符串，则输出 “-1”（不含引号）。否则，在第一行输出一个整数 $k$，表示所需的最少操作次数。在接下来的 $k$ 行中，每行输出两个整数 $l$ 和 $r$，表示一次操作。如果存在多种可能的答案，输出其中任意一个即可。

样例

输入格式 1

001122

输出格式 1

2
4 5
1 1

输入格式 2

000022

输出格式 2

-1