Description:
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.
Input Format:
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$$$.
Output Format:
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.
Note:
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}$$$.