基因

题目描述

有一个长度为 $n$ 的字符串 $S$，其中只包含大写字母。

小 A 将 $S$ 翻转后，得到另一个字符串 $S'$。两个字符串 $S$ 与 $S'$ 对应配对（即 $S_i$ 与 $S'_i$ 配对，$S'_i = S_{n+1-i}$）。

配对规则如下：

• 定义 $\tt A$ 与 $\tt T$，$\tt C$ 与 $\tt G$ 为可以配对的字母。
• 如果 $S_i$ 与 $S_i'$ 为可以配对的字母，那么该字符串的稳定性增加 $i$。
• 如果 $S_i$ 或者 $S_i'$ 中任意一方出现非 $\tt A,\tt T,\tt C,\tt G$ 的字母，则整个字符串的稳定性将直接为 $0$。

现在给定 $T$ 个字符串 $S$，对每一个字符串，询问若用其翻转再进行配对，其稳定性将如何。

输入格式

第一行输入一个正整数 $T$，表示给定多少个字符串。对于每一个字符串：

• 第一行输入一个正整数 $n$，表示字符串的长度；
• 第二行输入一个字符串 $S$，表示该字符串。

输出格式

对于每个字符串，输出一行一个整数，表示若用其翻转再进行配对，其稳定性将如何。

样例 #1

输入 #1

3
5
ATCGT
6
ACATGT
5
ATCGU

输出 #1

6
21
0

说明/提示

【样例解释】

• 对于第一个字符串，$S=\tt{ATCGT}$，$S'=\tt{TGCTA}$。可以配对的位置是第 $1$ 个（$\tt A$ 与 $\tt T$）和第 $5$ 个（$\tt T$ 与 $\tt A$），因此稳定性是 $1+5=6$。
• 对于第二个字符串，$S=\tt{ACATGT}$，$S'=\tt{TGTACA}$，每个对应位置上的字母都可以配对，因此稳定性是 $1+2+3+\dots+6=21$。
• 对于第三个字符串，出现了非 $\tt A,\tt T,\tt C,\tt G$ 的字母 $\tt U$，因此稳定性为 $0$。

【数据范围】

对于所有数据，保证：$1\leq T\leq 5$，$1\leq n\leq 10^5$，$S$ 中出现的所有字母保证为大写英语字母。

注意答案可能超过 $32$ 位整数范围，请使用 $64$ 位整数（long long）存储答案。