Acesrc 是南京大学一位首屈一指的著名字符串理论家。他坚持认为重要的事情应该说 $k$ 遍。他还认为，任何可以通过将某个非空字符串重复拼接 $k$ 次而得到的字符串都是“绚丽的”（splendid）。因此，他总是教导新人：“字符串理论问题很重要！字符串理论问题很重要！……字符串理论问题很重要！”

今天，他想考察新人是否记住了他的教导。他给出了一个由小写字母组成的字符串，并询问他们该字符串中“绚丽的”子串的数量。没有人能解决这个问题，他们将被训斥数小时。你能帮他们解决这个问题吗？

注意：出现在不同位置的相同“绚丽的”子串应分别计数。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。每个测试用例的第一行包含一个整数 $k$ ($1 \le k \le 20$)。每个测试用例的第二行是一个仅由小写字母组成的字符串 $S$，其长度在 $1$ 到 $3 \times 10^5$ 之间（包含边界）。所有测试用例中字符串长度之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

样例输入 1

3
2
aabb
2
abababab
3
abc

样例输出 1

2
6
0