#include <bits/stdc++.h>
#define LL long long
#define mes(s, x) memset(s, x, sizeof(s))
using namespace std;
inline LL read(){char c;c = getchar();while(!(('0' <= c && c <= '9') || c == '-')) c = getchar();bool flag = 0;if(c == '-'){flag = 1;c = getchar();}LL tot = 0;while('0' <= c && c <= '9'){tot = 10 * tot + c - '0';c = getchar();}return flag ? -tot : tot;}
inline void _write(LL i){if(i == 0) return;_write(i / 10);putchar(i % 10 + '0');return;}
inline void write(LL i){if(i == 0) putchar('0');else if(i < 0){putchar('-');_write(-i);}else _write(i);return;}
char s[100005];
int lnk[200010], len[200010], nxt[200010][26], siz[200010], b[100010], cnt;
vector<int> ch[200010];
void dfs(int i){
	int x;
	for(int j = 0; j < ch[i].size(); j++){
		x = ch[i][j];
		dfs(x);
		siz[i] += siz[x];
	}
	return; 
}
int main(){
	int t = read(), n, k, c, cur, q, p, clone, ans;
	while(t--){
		mes(lnk, 0);
		mes(len, 0);
		mes(nxt, 0);
		mes(siz, 0);
		mes(b, 0);
		scanf("%s %d", s + 1, &k);
		n = strlen(s + 1);
		cnt = p = 0;
		for(int i = 1; i <= n; i++){
			len[++cnt] = len[p] + 1;
			cur = cnt;
			c = s[i] - 'a';
			while(1){
				if(!nxt[p][c]) nxt[p][c] = cur;
				else{
					q = nxt[p][c];
					if(len[q] == len[p] + 1){
						lnk[cur] = q;
						break;
					}else{
						clone = ++cnt;
						for(int j = 0; j < 26; j++){
							nxt[clone][j] = nxt[q][j];
						}
						len[clone] = len[p] + 1;
						lnk[clone] = lnk[q];
						lnk[cur] = lnk[q] = clone;
						while(1){
							if(nxt[p][c] == q) nxt[p][c] = clone;
							if(p == 0) break;
							p = lnk[p];
						}
						break;
					}
				}
				if(p == 0) break;
				p = lnk[p]; 
			}
			siz[cur] = 1;
			p = cur;
		}
		for(int i = 1; i <= cnt; i++) ch[lnk[i]].push_back(i);
		dfs(0);
		for(int i = 1; i <= cnt; i++){
			if(siz[i] == k){
				b[len[lnk[i]] + 1]++;
				b[len[i] + 1]--;
			}
		}
		for(int i = 1; i <= n; i++) b[i] += b[i - 1];
		ans = 0;
		for(int i = 1; i <= n; i++) if(b[i] && b[i] >= b[ans]) ans = i;
		if(ans == 0) ans = -1; 
		printf("%d\n", ans);
		for(int i = 0; i <= cnt; i++) ch[i].clear();
	}
	return 0;
}