rt

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 100005;

int T, n, K;
char s[MAXN];

class Suffix_automaton {
	public : 
	int idx, root;
	private : 
	struct Node {
		int len, cnt;
		int fail, sons[28];
	}tr[MAXN << 1]; int lst;
	inline int NewNode(int ln) {
		tr[++ idx].len = ln;
		tr[idx].fail = 0;
		memset(tr[idx].sons, 0, sizeof(tr[idx].sons));
		return idx;
	}
	public : 
	inline Node& operator [] (const int &x) {
		return tr[x];
	}
	inline void Init() {
		for (int i = 1; i <= idx; ++ i)
			tr[i].len = tr[i].cnt = tr[i].fail = 0, 
			memset(tr[i].sons, 0, sizeof(tr[i].sons));
		idx = 0; root = lst = NewNode(0);
	}
	inline void Insert(int x) {
		int p = lst, cur = NewNode(tr[p].len + 1);
		tr[cur].cnt = 1;
		while (p && !tr[p].sons[x]) 
			tr[p].sons[x] = cur, p = tr[p].fail;
		if (!p) tr[cur].fail = 1;
		else {
			int q = tr[p].sons[x];
			if (tr[q].len == tr[p].len + 1)
				tr[cur].fail = q;
			else {
				int nq = NewNode(tr[p].len + 1);
				tr[nq].fail = tr[q].fail;
				memcpy(tr[nq].sons, tr[q].sons, sizeof(tr[p].sons));
				tr[q].fail = tr[cur].fail = nq;
				while (p && tr[p].sons[x] == q)
					tr[p].sons[x] = nq, p = tr[p].fail;
			}
		}
		lst = cur;
	}
}SAM;

int ans[MAXN];
inline void Calc() {
	for (int i = 1; i <= n; ++ i)
		ans[i] = 0;
	for (int i = SAM.idx; i; -- i) {
		SAM[SAM[i].fail].cnt += SAM[i].cnt;
		if (SAM[i].cnt == K) 
			-- ans[SAM[i].len + 1], 
			++ ans[SAM[SAM[i].fail].len + 1];
	}
	for (int i = 1; i <= n; ++ i)
		ans[i] += ans[i - 1];
}

inline void Solve() {
	scanf ("%s", s + 1); 
	n = strlen(s + 1); scanf ("%d", &K);
	SAM.Init();
	for (int i = 1; i <= n; ++ i)
		SAM.Insert(s[i] - 'a');
	Calc();
	int mx = 1, ln = -1;
	for (int i = 1; i <= n; ++ i)
		if (ans[i] >= mx) 
			mx = ans[i], ln = i;
	printf ("%d\n", ln);
}

int main()
{
	scanf ("%d", &T);
	while (T --) Solve();
	return 0;
}