给定一个长度为 的字符串 ，您可以将 左移至多 次（包括零次）。求操作之后，字符串中最多含有几个 nanjing 子串。
nanjing
更正式地，令 表示将 左移 次后获得的字符串。也就是说 。令 。令 表示整数对 的数量，满足 且 。找到一个整数 满足 并最大化 。输出这个最大化的值。
有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据：
第一行输入两个整数 和 （，），表示字符串的长度和最多能进行几次左移操作。
第二行输入一个长度为 的字符串 。字符串由小写英文字母组成。
保证所有数据 之和不超过 。
每组数据输出一行一个整数，表示字符串中最多含有几个 nanjing 子串。
4 21 10 jingicpcnanjingsuanan 21 0 jingicpcnanjingsuanan 21 3 nanjingnanjingnanjing 4 100 icpc
2 1 3 0
对于第一组样例数据，我们可以将字符串左移 次，得到字符串 pcnanjingsuananjingic。其中有两个 nanjing 子串。
pcnanjingsuananjingic
对于第二组样例数据，因为 ，我们无法进行任何左移操作。原字符串中有一个 nanjing 子串。
