#3108. 「TJOI2019」甲苯先生和大中锋的字符串

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: LoveAmy

题目描述

大中锋有一个长度为 n 的字符串,他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长,大中锋很难将这些子串一一尝试。

这天大中锋找到甲苯先生算命,但是甲苯先生说:「天机不可泄漏」。在大中锋的苦苦哀求下,甲苯先生告诉大中锋:「密码是在字符串中恰好出现了 k 次的子串」。

但是大中锋不知道该怎么做,在大中锋再三的恳求下,甲苯先生看其真诚,又告诉他:「在恰好出现了 k 次的子串中,你去按照字串的长度分类,密码就在数量最多的那一类里」。

大中锋为了尝试这个密码,想让你帮忙找出子串长度出现次数最多的长度数(如果有多个输出最长长度)。

输入格式

第一行一个正整数 T ,表示有 T 组测试数据。

接下来 T 行,每行包含一个字符串和一个正整数 k

输出格式

一共输出 T 行,每行一个整数表示在出现 k 次的子串中出现次数的最多的长度。

如果不存在子串出现 k 次,则输出 −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

数据范围与提示

对于 20\% 的数据, 1 ≤ k ≤ n ≤ 10

对于 100\% 的数据, 1 ≤ n ≤ 10^5,1 ≤ T ≤ 100,\sum n ≤ 3 \times 10^6