A large binary number is represented by a string \(A\) of size \(N\) and comprises of \(0_s\) and \(1_s\). You must perform a cyclic shift on this string. The cyclic shift operation is defined as follows:

If the string \(A\) is \([A_0, A_1, A_2,..., A_{N-1}]\), then after performing one cyclic shift, the string becomes \( [A_1, A_2, ..., A_{N-1}, A_0]\).

You performed the shift infinite number of times and each time you recorded the value of the binary number represented by the string. The maximum binary number formed after performing (possibly \(0\)) the operation is \(B\). Your task is to determine the number of cyclic shifts that can be performed such that the value represented by the string \(A\) will be equal to \(B\) for the \(K^{th}\) time.

Video approach to solve this question: here

Input format

First line: A single integer \(T\) denoting the number of test cases
For each test case:
- First line: Two space-separated integers \(N\) and \(K\)
- Second line: \(A\) denoting the string

Output format

For each test case, print a single line containing one integer that represents the number of cyclic shift operations performed such that the value represented by string \(A\) is equal to \(B\) for the \(K^{th}\) time.

Constraints

\(1 \le T \le 10^3\\ 1 \le N \le 10^5\\ 1 \le K \le 10^9\)

\(A_i = \{0,1\}\), for each \(i\)

Note: Sum of \(N\) overall test cases does not exceed \(10^5\)