3800: 砖块摆放(第五轮02)

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

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

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

1.   若相邻的两块砖块是相同颜色，那么这两块方砖紧挨的上面的砖块也将会是相同的颜色

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

现在告诉你最下面一层的 n  个砖块颜色（红黄蓝分别用  A 、B 、C  表示），需要你推出塔顶

部的颜色。爬到塔顶的牛牛已经看到了顶部砖块颜色， 并且偷偷告诉了你，作为本题的提示 ——它说它看到的是灰色（因为牛牛是色盲）。既然你已经有了提示， 我相信你一定能做出 这道题。

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

1.in 符合第一组数据的范围，

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

sample.zip

题目包含多组数据，第一行先输入一个正整数 t(t  ≤  10)  表示测试的组数。 对于每组数据而言：

第一行输入两个正整数 N  ，代表字符串长度  (1 ≤ N  ≤ 2 ×  10^5)

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

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

2
5
ABACC 
4
ACAB

C 
C