C. Kevin and Binary Strings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kevin discovered a binary string $$$s$$$ that starts with 1 in the river at Moonlit River Park and handed it over to you. Your task is to select two non-empty substrings$$$^{\text{∗}}$$$ of $$$s$$$ (which can be overlapped) to maximize the XOR value of these two substrings.

The XOR of two binary strings $$$a$$$ and $$$b$$$ is defined as the result of the $$$\oplus$$$ operation applied to the two numbers obtained by interpreting $$$a$$$ and $$$b$$$ as binary numbers, with the leftmost bit representing the highest value. Here, $$$\oplus$$$ denotes the bitwise XOR operation.

The strings you choose may have leading zeros.

$$$^{\text{∗}}$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

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

The only line of each test case contains a binary string $$$s$$$ that starts with 1 ($$$1\le\lvert s\rvert\le 5000$$$).

It is guaranteed that the sum of $$$\lvert s\rvert$$$ over all test cases doesn't exceed $$$5000$$$.

Output

For each test case, output four integers $$$l_1, r_1, l_2, r_2$$$ ($$$1 \le l_1 \le r_1 \le |s|$$$, $$$1 \le l_2 \le r_2 \le |s|$$$) — in the case the two substrings you selected are $$$s_{l_1} s_{l_1 + 1} \ldots s_{r_1}$$$ and $$$s_{l_2} s_{l_2 + 1} \ldots s_{r_2}$$$.

If there are multiple solutions, print any of them.

Example
Input
5
111
1000
10111
11101
1100010001101
Output
2 2 1 3
1 3 1 4
1 5 1 4
3 4 1 5
1 13 1 11
Note

In the first test case, we can choose $$$ s_2=\texttt{1} $$$ and $$$ s_1 s_2 s_3=\texttt{111} $$$, and $$$ \texttt{1}\oplus\texttt{111}=\texttt{110} $$$. It can be proven that it is impossible to obtain a larger result. Additionally, $$$ l_1=3$$$, $$$r_1=3$$$, $$$l_2=1$$$, $$$r_2=3 $$$ is also a valid solution.

In the second test case, $$$ s_1 s_2 s_3=\texttt{100} $$$, $$$ s_1 s_2 s_3 s_4=\texttt{1000} $$$, the result is $$$ \texttt{100}\oplus\texttt{1000}=\texttt{1100} $$$, which is the maximum.