小海和他朋友偶然间获得了一张藏宝图，他们提议根据藏宝图去寻宝，很快他们就准备好了，他们根据藏宝图的提示一路找寻，最终在藏宝图最终显示的地点找到了宝藏。当他们要打开宝藏的时候发现一张纸条，纸条上面有n组字符串，他们猜测这是藏宝箱的密码，但是密码只可能是这n组字符串中某一串字符串中的某一个子串；由于字符串很长很多他们不可能将这些子串去逐一的尝试，于是他们便将藏宝箱带回家去询问解密高手，解密高手告诉他们“密码在字符串中恰好出现了k次的子串”，小海他们一行几个人听的一头雾水的，不知道该怎么做，又去不断地询问解密大师，解密大师又告诉他们“密码在恰好出现 k次的子串中，你们去按照字串的长度分类，密码就在数量最多的那一类里面”。
小海迫切的想知道密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出，最长长度），若未找到则输出-1。

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

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

【样例解释】
对于第一个数据：其中子串 b, aa, ab, aab 均只出现一次，其中长度为 1 的子串出现了1次，长度为2的子串出现了2次，长度为 3 的子串出现了1次。所以答案为 2 。
对于第二个数据：其中子串 a, b, c, ab, bc, abc 均只出现一次，其中长度为1的子串出现了3次，长度为2的子串出现了 2 次，长度为 3 的子串出现了1次。所以答 案为 1 。
对于第三个数据：其中子串aaa出现二次，长度为3的子串出现了1次，其他长度均没有。所以答案为 3。
对于第四个数据：其中子串a, b, ab出现二次，其中长度为1的子串出现了2次，长度为2的子串出现了1次。所以答案为 1 。
对于第五个数据：其中子串 b, c, ab, ba 出现二次，其中长度为1的子串出现了2次，长度为2的子串出现了2次。所以答案为2 。
对于第六个数据：其中子串没有出现四次。所以本题的本题的答案为 −1 。
【数据范围】
对于20%的数据，1 ≤ k ≤ n ≤ 10。
对于100%的数据，1 ≤ n ≤10^5, Σ n ≤3 X 10^6，1≤k≤20，输入的字符串中仅包含小写英文字母。
对于100%的数据，每组字符串的长度均不超过100。

NOI省选