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.
输入解释
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$.
输出解释
For each test case, print the number of the important substrings in a line.