#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int T, K, n;
char s[N];
int rk[N], id[N], oldrk[N], cnt[N], sa[N], height[N], key1[N], m, p;
bool cmp(int x, int y, int w){
	return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
int f[N][20];
void make_st(){
	for(int i = 1; i <= n; i++)
		f[i][0] = height[i];
	for(int j = 1; j <= 19; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
			f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}
int ask(int l, int r){
	int k = log2(r - l + 1);
	return min(f[l][k], f[r - (1<<k) + 1][k]);
}
long long b[N];
signed main(){
	scanf("%lld", &T);
	while(T--){
		scanf("\n%s %lld", s + 1, &K);
		n = strlen(s + 1);
		m = 256;
		memset(cnt, 0, sizeof(cnt));
		for(int i = 1; i <= n; i++)
			cnt[rk[i] = s[i]]++;
		for(int i = 1; i <= m; i++)
			cnt[i] += cnt[i-1];
		for(int i = 1; i <= n; i++)
			sa[cnt[s[i]]--] = i;
		for(int w = 1; ; w <<= 1, m = p){
			p = 0;
			for(int i = n; i + w > n; i--)
				id[++p] = i;
			for(int i = 1; i <= n; i++)
				if(sa[i] - w > 0)
					id[++p] = sa[i] - w;
			memset(cnt, 0, sizeof(cnt));
			for(int i = 1; i <= n; i++)
				cnt[key1[i] = rk[id[i]]]++;
			for(int i = 1; i <= m; i++)
				cnt[i] += cnt[i-1];
			for(int i = n; i >= 1; i--)
				sa[cnt[key1[i]]--] = id[i];
			memcpy(oldrk + 1, rk + 1, sizeof(int) * n);
			p = 0;
			for(int i = 1; i <= n; i++)
				rk[sa[i]] = cmp(sa[i], sa[i-1], w) ? p : ++p;
			if(p == n)
				break;
		}
		for(int i = 1, k = 0; i <= n; i++){
			if(rk[i] == 0)
				continue;
			if(k)
				k--;
			while(s[i + k] == s[sa[rk[i] - 1] + k])
				k++;
			height[rk[i]] = k;
		}
		make_st();
		memset(b, 0, sizeof(b));
		for(int i = K; i <= n; i++){
			int L = i - K + 1, R = i;
			int r = n - sa[R] + 1;
			if(K != 1)
				r = ask(L + 1, R);
			int l = max(height[L], height[R + 1]) + 1;
			if(l <= r){
				b[l]++;
				b[r + 1]--;
			}
		}
		for(int i = 1; i <= n; i++)
			b[i] += b[i-1];
		b[0] = 1;
		int ans = 0;
		for(int i = 1; i <= n; i++)
			if(b[i] >= b[ans])
				ans = i;
		if(ans)
			printf("%lld\n", ans);
		else
			puts("-1");
	}
	return 0;
}