#include <bits/stdc++.h>
#define akemi namespace
#define homula std
using akemi homula;
int t,k,len;
char s[100005];
int tot=1,lst=1;
struct node{
	int fa,len,ch[26];
	void init(){
		fa=len=0;
		for(int i=0;i<26;i++) ch[i]=0;
	}
}tr[200006];
int dp[200006];
void insert(int c){
	int p=lst,np=lst=++tot;
	dp[np]=1;
	tr[np].len=tr[p].len+1;
	for(;p&&!tr[p].ch[c];p=tr[p].fa) tr[p].ch[c]=np;
	if(!p) tr[np].fa=1;
	else{
		int q=tr[p].ch[c];
		if(tr[q].len-1==tr[p].len){
			tr[np].fa=q;
		}
		else{
			int nq=++tot;
			tr[nq]=tr[q];
			tr[nq].len=tr[p].len+1;
			tr[q].fa=tr[np].fa=nq;
			for(;p&&tr[p].ch[c]==q;p=tr[p].fa) tr[p].ch[c]=nq;
		}
	}
}

int head[200006],ecnt;
struct edge{
	int nxt,v;
}e[200006];
void add(int u,int v){
	e[++ecnt].v=v;
	e[ecnt].nxt=head[u];
	head[u]=ecnt;
}
int cnt[200006];
void dfs(int u){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		dfs(v);
		dp[u]+=dp[v];
	}
	if(u!=1&&dp[u]==k){
		cnt[tr[u].len+1]--;
		cnt[tr[tr[u].fa].len+1]++;
	}
}

int main(){
	cin>>t;
	while(t--){
		scanf("%s",s+1);
		len=strlen(s+1);
		cin>>k;
		tot=1,lst=1;
		for(int i=1;i<=len;i++){
			insert(s[i]-'a');
		}
		for(int i=2;i<=tot;i++){
			add(tr[i].fa,i);
		}
		dfs(1);
		int mx=0;
		for(int i=1;i<=len;i++){
			cnt[i]+=cnt[i-1];
			mx=max(mx,cnt[i]);
		}
		int ans=0;
		for(int i=1;i<=len;i++){
			if(mx==cnt[i]) ans=i;
		}
		if(mx==0) cout<<-1<<endl;
		else cout<<ans<<endl;
		for(int i=1;i<=tot;i++){
			tr[i].init();
			dp[i]=head[i]=0;
		}
		for(int i=1;i<=len;i++) cnt[i]=0;
	}
}