5659 - 提高:Manacher 算法:回文子串

给你一个字符串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

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题