砖块摆放

题目描述

有一个 $n$ 层的塔，从上往下数的第 $i$ 层有 $i$ 个砖块，由于塔太高了，我们只能看到最后一层，也就是第 $n$ 层的砖块。

除了最后一层的砖块外，每一个砖块都和下面一层的两个砖块相邻，呈现这样的形状：

塔上面只有红黄蓝三种颜色的砖块，并且有以下规律：

1. 若相邻的两块砖块是相同颜色，那么这两块方砖紧挨的上面的砖块也将会是相同的颜色。
2. 若相邻的两块砖块是不同颜色，那么这两块方砖紧挨的上面的砖块将会是没有出现的第三种颜色。

现在告诉你最下面一层的 $n$ 个砖块颜色（红黄蓝分别用 A、B、C 表示），需要你推出塔顶部的颜色。爬到塔顶的牛牛已经看到了顶部砖块颜色，并且偷偷告诉了你，作为本题的提示——它说它看到的是灰色（因为牛牛是色盲）。既然你已经有了提示，我相信你一定能做出这道题。

大样例：共有三个大样例，

• 1.in 符合第一组数据的范围，
• 5.in 符合第五组数据的范围，也就是字符串仅包含两种字符，
• 7.in 符合满分的数据范围。

sample.zip

输入格式

题目包含多组数据，第一行先输入一个正整数 $t(t\le10)$ 表示测试的组数。

对于每组数据而言：

第一行输入两个正整数 $N$，代表字符串长度（$1\le N\le2\times10^5$）。

第二行输入长度为 $N$ 的字符串 $S$，字符串仅由颜色的首字母 A、B、C 构成。

输出格式

对于每一组数据，输出一行一个字母表示答案。

样例 1

输入

2
5
ABACC
4
ACAB

输出

C
C

说明

第一个数据说明：倒数第二层是 CCBC，倒数第三层是 CAA，倒数第二层是 BA，最顶层是 C。

备注

对于 $20\%$ 的数据，有 $n\le1000$。

对于另外 $20\%$ 的数据，字符串仅包含两种字符且交替出现，形如 ABABABABABAB...。

对于另外 $20\%$ 的数据，字符串仅包含两种字符。

对于 $100\%$ 的数据，有 $n\le2\times10^5$。