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

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

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}$.

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