小海和他朋友偶然间获得了一张藏宝图,他们提议根据藏宝图去寻宝,很快他们就准备好了,他们根据藏宝图的提示一路找寻,最终在藏宝图最终显示的地点找到了宝藏。当他们要打开宝藏的时候发现一张纸条,纸条上面有n组字符串,他们猜测这是藏宝箱的密码,但是密码只可能是这n组字符串中某一串字符串中的某一个子串;由于字符串很长很多他们不可能将这些子串去逐一的尝试,于是他们便将藏宝箱带回家去询问解密高手,解密高手告诉他们“密码在字符串中恰好出现了k次的子串”,小海他们一行几个人听的一头雾水的,不知道该怎么做,又去不断地询问解密大师,解密大师又告诉他们“密码在恰好出现 k次的子串中,你们去按照字串的长度分类,密码就在数量最多的那一类里面”。
小海迫切的想知道密码,想让你帮忙找出子串长度出现次数最多的长度数(如果有多个输出,最长长度),若未找到则输出-1。
第一行一个正整数 n,表示有 n 组测试数据。
接下来 n 行每行包含一个字符串和一个正整数k 。
一共输出 n 行,每行一个整数表示在出现 k 次的子串中出现次数的最多的长度。 如果不存在子串出现k次,则输出 −1 。
6 aab 1 abc 1 aaaa 2 abab 2 ababacc 2 abab 4
2 1 3 1 2 -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省选