311387: CF1979D. Fixing a Binary String

D. Fixing a Binary Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a binary string $s$ of length $n$, consisting of zeros and ones. You can perform the following operation exactly once:

1. Choose an integer $p$ ($1 \le p \le n$).
2. Reverse the substring $s_1 s_2 \ldots s_p$. After this step, the string $s_1 s_2 \ldots s_n$ will become $s_p s_{p-1} \ldots s_1 s_{p+1} s_{p+2} \ldots s_n$.
3. Then, perform a cyclic shift of the string $s$ to the left $p$ times. After this step, the initial string $s_1s_2 \ldots s_n$ will become $s_{p+1}s_{p+2} \ldots s_n s_p s_{p-1} \ldots s_1$.

For example, if you apply the operation to the string 110001100110 with $p=3$, after the second step, the string will become 011001100110, and after the third step, it will become 001100110011.

A string $s$ is called $k$-proper if two conditions are met:

• $s_1=s_2=\ldots=s_k$;
• $s_{i+k} \neq s_i$ for any $i$ ($1 \le i \le n - k$).

For example, with $k=3$, the strings 000, 111000111, and 111000 are $k$-proper, while the strings 000000, 001100, and 1110000 are not.

You are given an integer $k$, which is a divisor of $n$. Find an integer $p$ ($1 \le p \le n$) such that after performing the operation, the string $s$ becomes $k$-proper, or determine that it is impossible. Note that if the string is initially $k$-proper, you still need to apply exactly one operation to it.

Input

Each test consists of multiple test cases. The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n$, $2 \le n \le 10^5$) — the length of the string $s$ and the value of $k$. It is guaranteed that $k$ is a divisor of $n$.

The second line of each test case contains a binary string $s$ of length $n$, consisting of the characters 0 and 1.

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

Output

For each test case, output a single integer — the value of $p$ to make the string $k$-proper, or $-1$ if it is impossible.

If there are multiple solutions, output any of them.

ExampleInput

7
8 4
11100001
4 2
1110
12 3
111000100011
5 5
00000
6 1
101001
8 4
01110001
12 2
110001100110

Output

3
-1
7
5
4
-1
3

Note

In the first test case, if you apply the operation with $p=3$, after the second step of the operation, the string becomes 11100001, and after the third step, it becomes 00001111. This string is $4$-proper.

In the second test case, it can be shown that there is no operation after which the string becomes $2$-proper.

In the third test case, if you apply the operation with $p=7$, after the second step of the operation, the string becomes 100011100011, and after the third step, it becomes 000111000111. This string is $3$-proper.

In the fourth test case, after the operation with any $p$, the string becomes $5$-proper.

题目大意：给定一个长度为 \( n \) 的二进制字符串 \( s \)，由 0 和 1 组成。你可以执行以下操作恰好一次：

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 \)-适当的，如果满足两个条件：

1. \( s_1=s_2=\ldots=s_k \)；
2. 对于任何 \( i \)（\( 1 \le i \le n - k \)），\( s_{i+k} \neq s_i \)。

例如，当 \( k=3 \) 时，字符串 \( 000 \)，\( 111000111 \) 和 \( 111000 \) 是 \( k \)-适当的，而字符串 \( 000000 \)，\( 001100 \) 和 \( 1110000 \) 不是。

给定一个整数 \( k \)，它是 \( n \) 的除数。找到一个整数 \( p \)（\( 1 \le p \le n \)），使得执行操作后，字符串 \( s \) 变为 \( k \)-适当的，或者确定这是不可能的。注意，如果字符串最初是 \( k \)-适当的，你仍然需要对它应用恰好一次操作。

输入输出数据格式：

输入：
- 第一行包含一个整数 \( 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 组成。

输出：
- 对于每个测试用例，输出一个整数——使字符串 \( k \)-适当的 \( p \) 的值，如果不可能则输出 -1。
- 如果有多个解，输出其中任何一个。题目大意：给定一个长度为 \( n \) 的二进制字符串 \( s \)，由 0 和 1 组成。你可以执行以下操作恰好一次： 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 \)-适当的，如果满足两个条件： 1. \( s_1=s_2=\ldots=s_k \)； 2. 对于任何 \( i \)（\( 1 \le i \le n - k \)），\( s_{i+k} \neq s_i \)。 例如，当 \( k=3 \) 时，字符串 \( 000 \)，\( 111000111 \) 和 \( 111000 \) 是 \( k \)-适当的，而字符串 \( 000000 \)，\( 001100 \) 和 \( 1110000 \) 不是。 给定一个整数 \( k \)，它是 \( n \) 的除数。找到一个整数 \( p \)（\( 1 \le p \le n \)），使得执行操作后，字符串 \( s \) 变为 \( k \)-适当的，或者确定这是不可能的。注意，如果字符串最初是 \( k \)-适当的，你仍然需要对它应用恰好一次操作。 输入输出数据格式： 输入： - 第一行包含一个整数 \( 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 组成。 输出： - 对于每个测试用例，输出一个整数——使字符串 \( k \)-适当的 \( p \) 的值，如果不可能则输出 -1。 - 如果有多个解，输出其中任何一个。