[TJOI2019]甲苯先生和大中锋的字符串
题号：NC50808
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

大中锋有一个长度为n的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长，大中锋很难将这些子串一一尝试。
这天大中锋找到甲苯先生算命，但是甲苯先生说：「天机不可泄漏」。在大中锋的苦苦哀求下，甲苯先生告诉大中锋：「密码是在字符串中恰好出现了k次的子串」。
但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：「在恰好出现了k次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里」。
大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。

输入描述:

第一行一个正整数T，表示有T组测试数据。
接下来T行，每行包含一个字符串和一个正整数k。

输出描述:

一共输出T行，每行一个整数表示在出现k次的子串中出现次数的最多的长度。
如果不存在子串出现k次，则输出−1。
示例1

输入

复制 
6
aab 1
abc 1
aaaa 2
abab 2
ababacc 2
abab 4

输出

复制 
2
1
3
1
2
-1

说明

对于第一个数据：其中子串\texttt{b,aa,ab,aab}均只出现一次，其中长度为1的子串出现了1次，长度为2的子串出现了2次，长度为3的子串出现了1次。所以答案为2。
对于第二个数据：其中子串\texttt{a,b,c,ab,bc,abc}均只出现一次，其中长度为1的子串出现了3次，长度为2的子串出现了2次，长度为3的子串出现了1次。所以答案为1。
对于第三个数据：其中子串\texttt{aaa}出现二次，长度为3的子串出现了1次，其他长度均没有。所以答案为3。
对于第四个数据：其中子串\texttt{a,b,ab}出现二次，其中长度为1的子串出现了2次，长度为2的子串出现了1次。所以答案为1。
对于第五个数据：其中子串\texttt{b,c,ab,ba}出现二次，其中长度为1的子串出现了2次，长度为2的子串出现了2次。所以答案为2。
对于第六个数据：其中子串没有出现四次。所以本题的本题的答案为-1。

备注:

对于的数据，1≤k≤n≤10；
对于的数据，。