题目描述

小 V 有一个长度为 $n$ 的字符串 $S$，其仅包含小写字母。他可以对这个串做以下两种操作任意次：

• 删除这个字符串的第一个字符；

• 删除这个字符串的第二个字符，然后把左右两部分拼接起来。

小 V 想知道他一共可以得到多少种不同的字符串？注意：空串不计入答案内。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每一组数据，第一行一个正整数 $n$，表示字符串长度。第二行输入一个长度为 $n$ 的仅包含小写英文字母的字符串。

输出格式

对于每一组数据，输出一行一个整数，表示答案。

输入样例

3
3
xyz
6
hhhhhh
1
a

输出样例

6
6
1

输入样例 #2

1
1
w

输出样例 #2

1

输入样例 #3

1
2
fh

输出样例 #3

3

说明提示

对于第一组数据，可以形成的字符串有：$xyz, yz, xz, x, y, z$。

对于第二组数据，可以形成的字符串为任意不超过 $6$ 个 $h$ 组成的字符串。

【数据范围与提示】

$\sum n$ 是指单个测试点的 $n$ 之和。

数据范围

• 对于 30% 的数据，$1 \le \sum n \le 1000$

• 对于 100% 的数据，$1\le n, \sum n \le 10^6, 1\le T \le 10000$