CF1684H.Hard Cut

You are given a binary string $s$ . You have to cut it into any number of non-intersecting substrings, so that the sum of binary integers denoted by these substrings is a power of 2. Each element of $s$ should be in exactly one substring.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^5$ ). Description of the test cases follows.

Each test case contains a binary string $s$ ( $1 \le |s| \le 10^6$ ).

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

For each test case output the answer to the problem as follows:

• If the answer does not exist, output $-1$ .
• If the answer exists, firstly output an integer $k$ — the number of substrings in the answer. After that output $k$ non-intersecting substrings, for $i$ -th substring output two integers $l_i, r_i$ ( $1 \le l_i, r_i \le |s|$ ) — the description of $i$ -th substring.

If there are multiple valid solutions, you can output any of them.

In the first test case it is impossible to cut the string into substrings, so that the sum is a power of 2.

In the second test case such cut is valid:

• $011_2 = 3_{10}$ ,
• $0_2 = 0_{10}$ ,
• $1_2 = 1_{10}$ .

$3 + 0 + 1 = 4$ , $4$ is a power of 2.