给定一个二进制字符串 $$$s$$$,长度为 $$$n$$$,由零和一组成。您可以仅执行一次以下操作:
1. 选择一个整数 $$$p$$$ ($$$1 \le p \le n$$$)。
2. 反转子字符串$$$s_1 s_2 \ldots s_p$$$。此步骤之后,字符串 $$$s_1 s_2 \ldots s_n$$$ 将变为 $$$s_p s_{p-1} \ldots s_1 s_{p+1} s_{p+2} \ldots s_n$$$。
3. 然后,将字符串 $$$s$$$ 向左循环移位 $$$p$$$ 次。完成此步骤后,初始字符串 $$$s_1s_2 \ldots s_n$$$ 将变为 $$$s_{p+1}s_{p+2} \ldots s_n s_p s_{p-1} \ldots s_1$$$。
例如,如果对字符串 110001100110 进行 $$$p=3$$$ 的运算,则经过第二步后,该字符串将变为 011001100110,经过第三步后,该字符串将变为 001100110011。
如果满足两个条件,则字符串 $$$s$$$ 被称为 $$$k$$$-proper:
- $$$s_1=s_2=\ldots=s_k$$$;
- $$$s_{i+k} \neq s_i$$$ 对于任何 $$$i$$$ ($$$1 \le i \le n - k$$$)。
例如,对于 $$$k=3$$$,字符串 000、111000111 和 111000 是 $$$k$$$ 正确的,而字符串 000000、001100 和 1110000 则不是。
给定一个整数 $$$k$$$,它是 $$$n$$$ 的除数。找到一个整数$$$p$$$ ($$$1 \le p \le n$$$),使得执行运算后,字符串$$$s$$$变为$$$k$$$-正确,或者确定不可能。请注意,如果字符串最初是 $$$k$$$-proper,您仍然需要对其应用一个操作。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n$$$, $$$2 \le n \le 10^5$$$) - 字符串 $$$s$$$ 的长度和 $$$k$$$ 的值。保证 $$$k$$$ 是 $$$n$$$ 的约数。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$,由字符0和1组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - $$$p$$$ 的值,以使字符串 $$$k$$$ 正确,如果不可能,则输出 $$$-1$$$。
如果有多个解,则输出其中任意一个。
示例
输入 #1
7 8 4 11100001 4 2 1110 12 3 111000100011 5 5 00000 6 1 101001 8 4 01110001 12 2 110001100110
输出 #1
3 -1 7 5 4 -1 3
注意
在第一个测试用例中,如果使用 $$$p=3$$$ 进行运算,则在运算的第二步之后,该字符串将变为 11100001,而在第三步之后,它将变为 00001111。该字符串是 $$$4$$$-proper。
在第二个测试用例中,可以看出没有经过任何操作,字符串就变成了 $$$2$$$-proper。
在第三个测试用例中,如果使用 $$$p=7$$$ 进行运算,则在第二步运算之后,该字符串将变为 100011100011,而在第三步之后,它将变为 000111000111。该字符串是 $$$3$$$-proper。
在第四个测试用例中,与任何 $$$p$$$ 操作后,字符串变为 $$$5$$$-proper。