// Problem: D. Fixing a Binary String
// Contest: Codeforces - Codeforces Round 951 (Div. 2)
// URL: https://codeforces.com/contest/1979/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define p_b push_back
#define ft first
#define nd second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define YES cout << "YES" << "\n"
#define NO cout << "NO" << "\n"

using namespace std;

typedef long long ll;

const ll mod = (ll)1000000363;
const ll P = 2;

ll sum[114514], h[114514], sum2[114514];

// ll qpow(ll a, ll b)
// {
	// ll ans = 1;
	// while (b)
	// {
		// if (b & 1) ans = ans * a % mod;
		// a = a % mod * a % mod;
		// b >>= 1;
	// }
	// return ans;
// }

void solve()
{
	int n, k;
	ll ht1 = 0, ht2 = 0, tsum = 0;
	cin >> n >> k;
	string s;
	cin >> s;
	string t1, t2, res;
	res = s;
	reverse(res.begin(), res.end());
	for (int i = 0; i < n; i++)
	{
		if ((i / k) % 2) t1 += '0', t2 += '1';
		else t1 += '1', t2 += '0';
		ht1 = (ht1 * P % mod + (t1[i] - '0') % mod) % mod;
		ht2 = (ht2 * P  % mod+ (t2[i] - '0') % mod) % mod;
		tsum = (tsum * P % mod + (s[i] - '0') % mod) % mod;
	}
	for (int i = 1; i <= n; i++)
	{
      //sum,sum2分别维护1-n的从后往前i位（Sp+1 - Sn）和(Sp - S1)的总hash值
		sum[i] = (sum[i - 1] % mod + (s[n - i] - '0') * h[i - 1] % mod) % mod;
		sum2[i] = (sum2[i - 1] % mod + (res[n - i] - '0') * h[i - 1] % mod) % mod; 
		// cout << sum[i] << " ";
	}
	for (int i = 1; i <= n; i++)
	{
		ll ans = sum[n - i] % mod * h[i] % mod + sum2[i] % mod;//我是两段加起来的
		if (ans == ht1 || ans == ht2)
		{
			cout << i << "\n";
			return ;
		}
		// cout << ans << " ";
	}
	// cout << "\n";
	// for (int i = 1; i <= n; i++)
		// cout << sum2[i] << " ";
	cout << -1 << "\n";
}

int main()
{
	int t;
	cin >> t;
	h[0] = 1;
	for (int i = 1; i <= 110000; i++)
	{
		h[i] = h[i - 1] % mod * P % mod;
	}
	while (t--)
	{
		solve();
	}
	return 0;
}