#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string S;
cin >> S;
int X, K;
cin >> K >> X;
map<char, int>P;
int length, f = 0;
int valofk = K;
for (int i = 0; i < S.length(); ++i)
{
P[S[i]]++;
if (P[S[i]] > X) {
if (K > 0) {
K--;
continue;
}
else {
f = 1; /*Case when K is completely exhausted*/
length = i-valofk;
break;
}
}
/*if (P[S[i]] > (K + X))
{
f = 1;
length = i - K;
break;
}*/
}
if (f == 0)
{ /*if f==0 implies... k is not exhausted...implies subtract from length total k used i.e.(valofk-K)*/
cout << S.length()-(valofk-K)<< endl;
/*cout << S.length() - K << endl;*/
}
else
{
cout << length << endl;
}
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkKewoJaW50IHQ7CgljaW4gPj4gdDsKCgl3aGlsZSAodC0tKQoJewoJCXN0cmluZyBTOwoJCWNpbiA+PiBTOwoKCQlpbnQgWCwgSzsKCQljaW4gPj4gSyA+PiBYOwoKCQltYXA8Y2hhciwgaW50PlA7CgkJaW50IGxlbmd0aCwgZiA9IDA7CgkJaW50IHZhbG9mayA9IEs7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBTLmxlbmd0aCgpOyArK2kpCgkJewoJCQlQW1NbaV1dKys7CgkJCWlmIChQW1NbaV1dID4gWCkgewoJCQkJaWYgKEsgPiAwKSB7CgkJCQkJSy0tOwoJCQkJCWNvbnRpbnVlOwoJCQkJfQoJCQkJZWxzZSB7CgkJCQkJZiA9IDE7ICAgICAgICAgICAgIC8qQ2FzZSB3aGVuIEsgaXMgY29tcGxldGVseSBleGhhdXN0ZWQqLwoJCQkJCWxlbmd0aCA9IGktdmFsb2ZrOwoJCQkJCWJyZWFrOwoJCQkJfQoJCQl9CgkJCQkvKmlmIChQW1NbaV1dID4gKEsgKyBYKSkKCQkJCXsKCQkJCQlmID0gMTsKCQkJCQlsZW5ndGggPSBpIC0gSzsKCQkJCQlicmVhazsKCQkJCX0qLwoJCX0KCgkJaWYgKGYgPT0gMCkKCQl7CS8qaWYgZj09MCBpbXBsaWVzLi4uIGsgaXMgbm90IGV4aGF1c3RlZC4uLmltcGxpZXMgc3VidHJhY3QgZnJvbSBsZW5ndGggdG90YWwgayB1c2VkIGkuZS4odmFsb2ZrLUspKi8KCQkJY291dCA8PCBTLmxlbmd0aCgpLSh2YWxvZmstSyk8PCBlbmRsOwoJCQkvKmNvdXQgPDwgUy5sZW5ndGgoKSAtIEsgPDwgZW5kbDsqLwoJCX0KCQllbHNlCgkJewoJCQljb3V0IDw8IGxlbmd0aCA8PCBlbmRsOwoJCX0KCX0KfQo=