String Theory

Time limit4sMemory limit512 MB

Summary

Count substrings of S that equal some nonempty string repeated exactly k times, counting each occurrence position separately.

Level: Hard9 of 10
Topics: String, String matching, Number theory, Math
Solved: No attempts yet

Problem

Acesrc is a famous string theorist at Nanjing University, second to none. He insists that an important thing should always be said $k$ times. He also believes that every string obtained by concatenating $k$ copies of some nonempty string is splendid. So he always teaches newcomers, "String theory problems are important! String theory problems are important! ... String theory problems are important!"

Today he wants to test whether the newcomers remember his instruction. He presents a string of lower case letters and asks them for the number of splendid substrings of the presented string. No one can solve this problem, and they will be scolded for hours. Can you help them solve it?

Note that equal splendid substrings that occur at different positions are counted separately.

Input

The first line of input contains a single integer $T$ $(1 \leq T \leq 10)$ , the number of test cases. Each test case starts with a line containing an integer $k$ $(1 \leq k \leq 20)$ . The second line of a test case is a string $S$ consisting of lower case letters only, with length between $1$ and $3 \times 10^5$ inclusive. The sum of the lengths of the strings in all test cases never exceeds $10^6$ .

Output

For each test case, print the answer as a single integer on a single line.

Examples1

Example 1
Input
```
3
2
aabb
2
abababab
3
abc
```
Expected output
```
2
6
0
```