string string string

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Uncle Mao is a wonderful ACMER. One day he met an easy problem, but Uncle Mao was so lazy that he left the problem to you. I hope you can give him a solution.
Given a string s, we define a substring that happens exactly $k$ times as an important string, and you need to find out how many substrings which are important strings.

Input

The first line contains an integer $T$ ($T\leq 100$) implying the number of test cases.
For each test case, there are two lines:
the first line contains an integer $k$ ($k\geq 1$) which is described above;
the second line contain a string $s$ ($length (s)\leq 10^5$).
It's guaranteed that $\sum{length(s)} \leq 2*10^6$.

Output

For each test case, print the number of the important substrings in a line.

Sample Input

2 2 abcabc 3 abcabcabcabc

Sample Output

6 9

Hint

liuyiding

Source

2017 ACM/ICPC Asia Regional Shenyang Online

提交代码