Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4079
Hello, Hello and Hello

Time Limit: 6 Seconds      Memory Limit: 131072 KB      Special Judge

A ternary string is a sequence of digits, where each digit is either $0$, $1$, or $2$.

Chiaki has a nonempty ternary string $s$. Initially, the characters are sorted in non-decreasing order (i.e. all $0$s appear before all $1$s and all $1$s appear before all $2$s). Chiaki would like to shuffle the characters such that no two consecutive characters have the same value using the following operation: choose two integers $l$ and $r$ ($l \le r$), take characters from position $l$ to position $r$ inclusively, and move them to the end of the string.

Chiaki would like to know the minimum number of operations needed.

Input

There are multiple test cases. The first line of input is an integer $T$ indicates the number of test cases. For each test case:

The first line contains a ternary string $s$ ($1 \le |s| \le 10^6$).

It is guaranteed that the sum of all $|s|$ does not exceed $10^6$.

Output

For each test case, output "-1" (without the quotes) if Chiaki can not shuffle the string using the operations described above. Otherwise, output an integer $k$ in the first line -- the minimum number of operations needed. Each of the next $k$ lines output two integers $l$ and $r$ -- denoting an operation.

Sample Input

2
001122
000022

Sample Output

2
4 5
1 1
-1

Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status