C. Kevin 和二进制串

时间限制：2 秒
内存限制：256 MB

Kevin 在月光河公园的河边发现了一个以 $1$ 开头的二进制串 $s$，并把它交给了你。你需要选择 $s$ 的两个非空子串（可以重叠），使得这两个子串代表的二进制数的 XOR 值最大。

两个二进制串 $a$ 和 $b$ 的 XOR 定义为：把 $a,b$ 看成二进制整数（最左边是最高位），对这两个整数做按位异或（$\oplus$） 运算的值。 你选出的串可以包含前导零。

$\ast$ 字符串 $a$ 是 $b$ 的子串，当且仅当 $a$ 可以由 $b$ 删除开头若干个（可零）、结尾若干个（可零）字符得到。

输入

每个测试点包含多组数据。 第一行一个整数 $t$（$1\le t\le 10^3$），表示测试用例数量。

每组数据一行，一个以 $1$ 开头的二进制串 $s$（$1\le |s|\le 5000$）。 保证所有测试用例的 $|s|$ 之和不超过 $5000$。

输出

对于每组数据，输出四个整数： $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|$，表示你选出的两个子串。

如果有多种最优答案，输出任意一种即可。

样例输入

5
111
1000
10111
11101
1100010001101

样例输出

2 2 1 3
1 3 1 4
1 5 1 4
3 4 1 5
1 13 1 11

说明

• 第一个样例：选子串 $s_2=1$ 和 $s_1s_2s_3=111$，$1\oplus 111=110$，可以证明是最大。
• 第二个样例：选 $100$ 和 $1000$，$100\oplus 1000=1100$，为最优。