CF1562C.Rings

Frodo was caught by Saruman. He tore a pouch from Frodo's neck, shook out its contents —there was a pile of different rings: gold and silver...

"How am I to tell which is the One?!" the mage howled.

"Throw them one by one into the Cracks of Doom and watch when Mordor falls!"

Somewhere in a parallel Middle-earth, when Saruman caught Frodo, he only found $n$ rings. And the $i$-th ring was either gold or silver. For convenience Saruman wrote down a binary string $s$ of $n$ characters, where the $i$-th character was 0 if the $i$-th ring was gold, and 1 if it was silver.

Saruman has a magic function $f$, which takes a binary string and returns a number obtained by converting the string into a binary number and then converting the binary number into a decimal number. For example, $f(001010) = 10, f(111) = 7, f(11011101) = 221$.

Saruman, however, thinks that the order of the rings plays some important role. He wants to find $2$ pairs of integers $(l_1, r_1), (l_2, r_2)$, such that:

• $1 \le l_1 \le n$, $1 \le r_1 \le n$, $r_1-l_1+1\ge \lfloor \frac{n}{2} \rfloor$
• $1 \le l_2 \le n$, $1 \le r_2 \le n$, $r_2-l_2+1\ge \lfloor \frac{n}{2} \rfloor$
• Pairs $(l_1, r_1)$ and $(l_2, r_2)$ are distinct. That is, at least one of $l_1 \neq l_2$ and $r_1 \neq r_2$ must hold.
• Let $t$ be the substring $s[l_1:r_1]$ of $s$, and $w$ be the substring $s[l_2:r_2]$ of $s$. Then there exists non-negative integer $k$, such that $f(t) = f(w) \cdot k$.

Here substring $s[l:r]$ denotes $s_ls_{l+1}\ldots s_{r-1}s_r$, and $\lfloor x \rfloor$ denotes rounding the number down to the nearest integer.

Help Saruman solve this problem! It is guaranteed that under the constraints of the problem at least one solution exists.

弗罗多被萨鲁曼抓住了。萨鲁曼从弗罗多的脖子上扯下一个袋子，抖出里面的东西——一堆各式各样的戒指：金戒指和银戒指……

“我怎么才能分辨出哪一枚是至尊魔戒？！”巫师怒吼道。

“把它们一个接一个地扔进末日裂罅，然后看魔多何时覆灭！”

在某个平行的中土世界里，当萨鲁曼抓住弗罗多时，他只找到了 $n$ 枚戒指。其中第 $i$ 枚戒指要么是金的，要么是银的。为方便起见，萨鲁曼写下了一个长度为 $n$ 的二进制字符串 $s$，其中第 $i$ 个字符为 0 表示第 $i$ 枚戒指是金的，为 1 表示是银的。

萨鲁曼拥有一种魔法函数 $f$，该函数接收一个二进制字符串，并将其先解释为一个二进制数，再将该二进制数转换为十进制整数后返回。例如，$f(001010) = 10$，$f(111) = 7$，$f(11011101) = 221$。

然而，萨鲁曼认为戒指的排列顺序具有某种重要意义。他希望找到两对整数 $(l_1, r_1)$ 和 $(l_2, r_2)$，满足以下条件：

• $1 \le l_1 \le n$，$1 \le r_1 \le n$，且 $r_1-l_1+1\ge \lfloor \frac{n}{2} \rfloor$；
• $1 \le l_2 \le n$，$1 \le r_2 \le n$，且 $r_2-l_2+1\ge \lfloor \frac{n}{2} \rfloor$；
• 两对 $(l_1, r_1)$ 和 $(l_2, r_2)$ 互不相同，即至少满足 $l_1 \neq l_2$ 或 $r_1 \neq r_2$ 中的一个；
• 设 $t$ 是 $s$ 的子串 $s[l_1:r_1]$，$w$ 是 $s$ 的子串 $s[l_2:r_2]$，则存在一个非负整数 $k$，使得 $f(t) = f(w) \cdot k$。

此处子串 $s[l:r]$ 表示 $s_l s_{l+1} \ldots s_{r-1} s_r$，而 $\lfloor x \rfloor$ 表示将 $x$ 向下取整（即取不大于 $x$ 的最大整数）。

请帮助萨鲁曼解决这个问题！题目保证在给定约束条件下至少存在一组解。

Each test contains multiple test cases.

The first line contains one positive integer $t$ ($1 \le t \le 10^3$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $n$ ($2 \le n \le 2 \cdot 10^4$) — length of the string.

The second line of each test case contains a non-empty binary string of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。

第一行包含一个正整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个正整数 $n$（$2 \le n \le 2 \cdot 10^4$）—— 字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的非空二进制字符串。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For every test case print four integers $l_1$, $r_1$, $l_2$, $r_2$, which denote the beginning of the first substring, the end of the first substring, the beginning of the second substring, and the end of the second substring, respectively.

If there are multiple solutions, print any.

对每个测试用例，输出四个整数 $l_1$、$r_1$、$l_2$、$r_2$，分别表示第一个子串的起始位置、第一个子串的结束位置、第二个子串的起始位置以及第二个子串的结束位置。

若存在多个解，输出任意一个即可。

In the first testcase $f(t) = f(1111) = 15$, $f(w) = f(101) = 5$.

In the second testcase $f(t) = f(111000111) = 455$, $f(w) = f(000111) = 7$.

In the third testcase $f(t) = f(0000) = 0$, $f(w) = f(1000) = 8$.

In the fourth testcase $f(t) = f(11011) = 27$, $f(w) = f(011) = 3$.

In the fifth testcase $f(t) = f(001111) = 15$, $f(w) = f(011) = 3$.

第一个测试用例中，$f(t) = f(1111) = 15$，$f(w) = f(101) = 5$。

第二个测试用例中，$f(t) = f(111000111) = 455$，$f(w) = f(000111) = 7$。

第三个测试用例中，$f(t) = f(0000) = 0$，$f(w) = f(1000) = 8$。

第四个测试用例中，$f(t) = f(11011) = 27$，$f(w) = f(011) = 3$。

第五个测试用例中，$f(t) = f(001111) = 15$，$f(w) = f(011) = 3$。