在滚动雪人游戏中,已经堆好了 n 个不同类型的雪人。这些雪人共有 A, B, C 三种不同的类型。滚动雪人游戏的规则是,在当前的雪人队列中,任意选择 2 个不同类型的雪人,将他们合并改造成与合并前的 2 种类型不同类型的一个新的雪人。例如,选择了 2 个不同类型的雪人,它们的类型分别为 A 和 B,则合并改造后的新的雪人的类型为 C。选择类型分别为 A 和 C,则合并改造后的类型为 B;选择类型分别为 B 和 C,则合并改造后的类型为 A。当雪人队列中只剩下同一种类型的雪人时,游戏结束。小明和小雪希望用最少的合并次数完成滚动雪人游戏。
滚动雪人游戏问题:对于给定的雪人队列,计算出用最少的合并次数完成滚动雪人游戏后,留在在雪人队列中的雪人类型。
输入格式
每个测试项有多组测试数据。每组测试数据的第一行有一个正整数 n,第二行是一个由大写英文字母 A
, B
, C
组成的,长度为 n 的字符串,表示初始雪人队列。
输出格式
对每组测试数据,依次输出对于给定的初始雪人队列,用最少的合并次数完成滚动雪人游戏后,留在在雪人队列中的雪人类型 A
, B
或 C
。如果不能确定最终的雪人类型,则输出大写英文字母 N
。
样例数据
样例输入
5
ABCCC
3
ABC
样例输出
C
N
子任务
测试数据中 20% 的数据满足 n≤1000。
测试数据中 100% 的数据满足 n≤10000。
注
- 赛时并未提供数据组数,“请选手自行评估”。