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 0s appear before all 1s and all 1s appear before all 2s). 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 ≤ 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.

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 ≤ |s| ≤ 106).
It is guaranteed that the sum of all |s| does not exceed 106.

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.

2
001122
000022

2
4 5
1 1
-1