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.