def manacher(_S):
    L = 2*len(_S)+1
    radius = [0]* L
    S = ['#'] * L
    for i in range(len(_S)):
        S[2*i+1] = _S[i]
    i = j = 0
    while i < L:
        while i-j >= 0 and i+j < L and S[i-j] == S[i+j]:
            j += 1
        radius[i] = j
        k = 1
        while i-k >= 0 and i+k < L and k+radius[i-k] < j:
            radius[i+k] = radius[i-k]
            k += 1
        i += k
        j -= k
    return radius

def solve(N,M,S):
    m1 = manacher(S)
    for i,m in enumerate(m1):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 1
    m2 = manacher(S+S)
    for i,m in enumerate(m2):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 2
    m3 = manacher(S+S+S)
    maxl = 0
    for i,m in enumerate(m3):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 3
        maxl = max(maxl,l)
    if maxl >= N:
        return 0--M//N
    else:
        return -1

T = int(input())
for _ in range(T):
    N,M = map(int,input().split())
    S = input()
    print(solve(N,M,S))