#1794. [语言月赛 202311] 基因

[语言月赛 202311] 基因

题目描述

有一个长度为 nn 的字符串 SS。其只包含有大写字母。

小 A 将 SS 进行翻转后,得到另一个字符串 S′S'。两个字符串 SS 与 S′S' 对应配对。例如说,对于 S=ATCGTS=\tt{ATCGT},则有 S′=TGCTAS'=\tt{TGCTA},SS 与 S′S' 进行配对。

对于两个字符串 S,S′S,S' 的第 ii(1≤i≤n1 \leq i \leq n)个字母,配对规则如下:

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

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

输入格式

第一行输入一个正整数 TT,表示给定多少个字符串。对于每一个字符串:

  • 第一行输入一个正整数 nn,表示字符串的长度;
  • 第二行输入一个字符串 SS,表示该字符串。

输出格式

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

样例

3
5
ATCGT
6
ACATGT
5
ATCGU
6
21
0

题目来源:洛谷 B3891