5659 - 提高：Manacher 算法：回文子串
时间限制 : 1 秒
内存限制 : 256 MB
给你一个字符串s 和一个整数k， 找到尽可能多的子串使得它没有长度大于等于 k 的回文子串(子串的子串长度都小于k)。
输入
第一个一个整数T，表示有T组数据 之后每组数据有2行，每行数据如下： 第一行一个整数K 第二行一个字符串
输出
输出T行，每行1个整数
样例
输入
3 3 bababe 4 abcbbcbc 3 aabacecc
输出
12 27 20
提示
数据范围 1≤t≤100
k≤∣s∣≤10^5
所有测试样例的字符串长度加起来总共不超过10^6