#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
struct state{
	int len,nxt[30],link;
}trie[N<<1];
int tot,lst;
long long dp[N<<1],cnt[N<<1],maxlen=0;
string s;
int t,sum,ans,pos;
vector<int>g[N<<1];
int k;
inline void init(){
	for(int i=0;i<=tot;i++){
		trie[i].len=trie[i].link=0;
		dp[i]=0;
		for(int j=0;j<26;j++){
			trie[i].nxt[j]=0;
		}
		g[i].clear();
	}
	trie[0].len=0;
	trie[0].link=-1;
	tot=1;
	lst=0;
	ans=0;
}
void extend(char c){
	int id=c-'a';
	int cur=++tot,p=lst;
	trie[cur].len=trie[lst].len+1;
	dp[cur]=1;
	while(p!=-1&&!trie[p].nxt[id]){
		trie[p].nxt[id]=cur;
		p=trie[p].link;
	}
	if(p==-1){
		trie[cur].link=0;
	}else{
		int q=trie[p].nxt[id];
		if(trie[q].len==trie[p].len+1){
			trie[cur].link=q;
		}else{
			int np=++tot;
			trie[np].len=trie[p].len+1;
			trie[np].link=trie[q].link;
			for(int i=0;i<26;i++){
				trie[np].nxt[i]=trie[q].nxt[i];
			}
			while(p!=-1&&trie[p].nxt[id]==q){
				p=trie[p].link;
			}
			trie[q].link=trie[cur].link=np;
		}
	}
	lst=cur;
}
void dfs(int u){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		dfs(v);
		dp[u]+=dp[v];
	}
	if(u!=0&&dp[u]==k){
		cnt[trie[u].len]++;
		cnt[trie[trie[u].link].len]--;	
	}
	maxlen=max(maxlen,1ll*trie[u].len);
}
int main(){
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		cin>>s;
		cin>>k;
		init();
		for(int i=0;i<s.size();i++){
			extend(s[i]);
		}
		for(int i=1;i<=tot;i++){
			g[trie[i].link].push_back(i);
		}
		maxlen=0;
		dfs(0);
		sum=0,ans=0,pos=-1;
		for(int i=maxlen;i>0;i--){
			sum+=cnt[i];
			cnt[i]=0;//init
			if(sum>ans){
				ans=sum;
				pos=i;
			}
		}
		cout<<pos<<'\n';
		for(int i=0;i<=tot;i++){
			dp[i]=0;
			g[i].clear();
		}
	}
	return 0;
}