Acesrc is a famous string theorist at Nanjing University second to none. He insists that we should always say an important thing kktimes. He also believes that every string that can be obtained by concatenating kk 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 examine whether the newcomers remember his instruction. He presents a string consisting of lower case letters and asks them 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 this problem?
Note that equal splendid substrings occurred in different positions should be counted separately.
Input
The first line of input consists of a single integer TT(1≤T≤10)(1≤T≤10), denoting the number of test cases. Each test case starts with a single line of an integer kk(1≤k≤20)(1≤k≤20). The second line of a test case is a string SS consisting of lower case letters only, the length of which is between 11 and 3×1053×105 inclusive. The sum of the lengths of strings in all test cases never exceeds 106106.
Output
For each test case, print the answer as a single integer in a single line.