CF1562C Rings

佛罗多被萨鲁曼抓住了。他从佛罗多的脖子上扯下一个袋子，抖了抖里面的东西--有一堆不同的戒指：金的、银的...... "我怎么分得清哪个才是唯一的？"法师嚎叫着。 "把它们一个个扔进末日裂缝，看着魔多沦陷吧！" 在平行的中土世界，萨鲁曼抓住弗罗多时，只找到了 n 个戒指。第 i 个戒指要么是金的，要么是银的。为了方便起见，萨鲁曼写下了一个由 n 个字符组成的二进制字符串 $ s $，其中第 i 个字符为 0，表示第 i 个戒指是金戒指；第 i 个字符为 1，表示第 i 个戒指是银戒指。 萨鲁曼有一个神奇的函数 $ f $，它接收一个二进制字符串，并通过将字符串转换成二进制数，然后再将二进制数转换成十进制数来返回一个数字。例如，$ f(001010) = 10，f(111) = 7，f(11011101) = 221 $ 。 然而，萨鲁曼认为指环的顺序起着重要作用。他想找到2对整数 $ (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_ls_{l+1}\ldots s_{r-1}s_r $ , 而 $ \lfloor x \rfloor $ 表示将数字舍入到最接近的整数. 帮助萨鲁曼解决这个问题！在问题的约束条件下，保证至少有一个解存在。

每个测试包含多个测试用例。 第一行包含一个正整数 $ t $ （$ 1 \le t \le 10^3 $ ），表示测试用例的数量。测试用例说明如下。 每个测试用例的第一行包含一个正整数 $ n $ （$ 2 \le n \le 2 \cdot 10^4 $）--字符串的长度。 每个测试用例的第二行包含一个长度为 $ n $ 的非空二进制字符串。 保证所有测试用例中 $ n $ 的总和不超过 $ 10^5 $ 。

为每个测试用例打印四个整数 $ l_1 $ , $ r_1 $ , $ l_2 $ , $ r_2 $，分别表示第一个子串的开头、第一个子串的结尾、第二个子串的开头和第二个子串的结尾。 如果有多个解，请打印任意一个。

在第一个测试案例中 $ 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 $ .