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

通过次数

1

提交次数

2

Time Limit : 1 秒
Memory Limit : 256 MB

给你一个字符串s 和一个整数k, 找到尽可能多的子串使得它没有长度大于等于 k 的回文子串(子串的子串长度都小于k)

Input

第一个一个整数T,表示有T组数据 之后每组数据有2行,每行数据如下: 第一行一个整数K 第二行一个字符串

Output

输出T行,每行1个整数

Examples

Input

3
3
bababe
4
abcbbcbc
3
aabacecc

Output

12
27
20

Hint

数据范围 1≤t≤100

k≤∣s∣≤10^5

所有测试样例的字符串长度加起来总共不超过10^6