#include<bits/stdc++.h>
using namespace std;
string s;
int k;
char a[11][50];
long b[11][50];
long z[11][50][100010];
long y[11][50];
long u[11][50];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s>>k;
		long e=0;
		long f=100010;
		long c=0;
		long g=0;
		long d=s.length();
		for(int j=0;j<d;j++){
			if(b[i][s[j]]==0){
				c++;
				z[i][s[j]][c]=j;
				b[i][s[j]]++;
			}
			else{
				c++;
				z[i][s[j]][c]=j;
				b[i][s[j]]++;
			}
			if(b[i][s[j]]==k){
				e++;
				g++;
				y[i][s[j]]=j-z[i][s[j]][g];
				u[i][e]=y[i][s[j]];
			}
			else if(b[i][s[j]]>k){
				g++;
				if(j-z[i][s[j]][g]<y[i][s[j]]){
					y[i][s[j]]=j-z[i][s[j]][g];
				}
			}
		}
		for(int t=1;t<=e;t++){
			f=(min(f,u[i][t]));
		}
		if(e==0){
			cout<<-1<<endl;
		}else{
			cout<<f+1<<endl;
		}
	}
}