题目描述

给你一个长度为 n 的字符串，允许你执行任意次（可以是 0 次）如下的操作：

1. 删除字符串的第一个字符
2. 删除字符串的第二个字符

最终，你可以得到多少个不一样的非空字符串呢？

输入格式

第一行一个正整数 $T$，表示有 $T$ 组数据 ( $1 \le T \le 100$ )

接下来每行有一个整数 $n$ 和一个字符串 $s$ ，（$1 \le n \le 10^5$，字符串 $s$ 只包含小写字母)

输出格式

输出 $T$ 行，每行一个整数，第 $i$ 行为第 $i$ 组数据的答案。

样例

5
5 aaaaa
1 z
5 ababa
14 bcdaaaabcdaaaa
20 abcdefghijklmnopqrst

5
1
9
50
210

样例解释

对于第 1 组数据，你可以得到的字符串有 {a，aa，aaa，aaaa，aaaaa}，所以答案是 5 。

对于第 2 组数据，删除第 1 个字符和第 2 个字符分别得到了 aaba 和 baba；基于这 2 个字符串继续删除，可以得到 aba(不同的删除“路径”得到相同的 aba 只算 1 次) 、 bba ；继续删除，可以得到 安aa,ba ；继续删除，可以得到 a、b，所以，这一组数据能够得到的字符串有{a,b,aa,ba,aba,bba,aaba,baba,ababa}，所以答案是 9 。