#1032. 删除字符

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tony102

题目描述

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

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

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

输入格式

第一行一个正整数 ,表示数据组数。

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

输出格式

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

样例

样例输入

3
3
xyz
6
hhhhhh
1
a

样例输出

6
6
1

样例解释

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

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

对于第二组数据,将两个 全部变为 ,这样恰好使得 增加 1。

数据范围与提示

  • 对于 30% 的数据,

  • 对于 100% 的数据,

是指单个测试点的 之和。