[TJOI2019] 甲苯先生和大中锋的字符串

题目背景

TJOI2019 D2T2 源文件名:substring.* 时间限制: 1s 内存限制: 128M

题目描述

大中锋有一个长度为 $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

输出样例 #1

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\leq k\leq n\leq 10$ 对于 $100\%$ 的数据, $1\leq n\leq 10^5,1 \leq T \leq 100,\sum n \leq 3 * 10^6$ ,输入的字符串中仅包含小写英文字母。