Description

给定一个长度为 $n$ 的仅包含小写英文字母的字符串 $S$。我们定义一个子串 $S[\ell \dots r]$（即从第 $\ell$ 个字符到第 $r$ 个字符形成的子串，满足 $1 \leq \ell \leq r \leq n$）是"自匹配子串"，当且仅当该子串的首字符和尾字符完全相同，即 $S[\ell] = S[r]$。

现在，请你计算：字符串 $S$ 中一共有多少个"自匹配子串"。

Format

Input

本题包含多组测试数据，第一行包含一个整数 $T$ 满足 $1\leq T\leq 1\times 10^4$，表示测试数据组数。

每组测试用例的第一行包含一个整数 $n$ 表示字符串大小，满足 $1\leq n \leq 2\times 10^5$。

第二行包含一个长度为 $n$ 字符串 $S$。

本题保证所有测试用例的 $n$ 总和不超过 $2\times 10^5$。

Output

对于每一组测试用例输出字符串 $S$ 中一共有多少个“自匹配子串”。

Samples

3
4
abaa
5
abcda
6
aeious

7
6
6