F. 简单字符串问题
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给你一个长度为$$$n$$$，只含小写字符的字符串$$$str$$$，你要统计满足如下条件的三元组$$$ \lt a,b,c \gt $$$的数量

  • $$$1\le a \lt b \lt c \le n $$$
  • $$$str[a]=str[b]$$$且$$$str[b]=str[c]$$$，其中$$$str[i]$$$代表从左往右起$$$str$$$的第$$$i$$$个字符，下标从$$$1$$$开始
  • $$$2b=a+c$$$
Input

第一行一个整数 $$$(1 \le T \le 10000)$$$,表示数据组数

每组测试数据占一行，分别为字符串长度$$$n(3 \le n \le 100000)$$$和字符串$$$str$$$

保证单个测试样例的字符串长度之和不超过100000

Output

每组数据输出$$$1$$$行，代表该样例中满足条件的三元组的数量

Example
Input
2
6 abcabc
6 abcbcb
Output
0
1
Note

注意，如果你想的只是朴素的$$$O(n^2)$$$枚举的方法来统计答案，那么请再仔细考虑。