Given a binary string S of length N and an integer M, we make up a binary string T by 
concatenating M copies of S together. For example, if S="10010" and M = 3, the T="100101001010010"

We define an index i is perfect if T[1]+T[2]+...T[i] = T[i+1]+T[i+2] + ... + T[N*M]
(Please note here T[1] is the first character of T and T[N*M] is the last one)

Please find the number of perfect index in T.  If no such index, output 0

The first line contains a single integer C   ( 1 <= C <= 100000 ) which is the number of test cases
the first line of each test case contains two integers N and M ( 1<=N, M <= 100000)
the second line of each test case is the binary string S (the length is N) 

for each test case output the number of perfect indices in T. 

In test 3: T="101101101". In this string, index 4 and index 5 are perfect; therefore the answer is 2