Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

dfs and similar

divide and conquer

math

*3400

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Hard Cut

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Example

Input

4 00000 01101 0111011001011 000111100111110

Output

-1 3 1 3 4 4 5 5 8 1 2 3 3 4 4 5 6 7 7 8 10 11 12 13 13 5 1 5 6 7 8 11 12 14 15 15

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2023 20:56:29 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|