题目描述

在献血活动中，以下血型是兼容的：

• 血型 A 的献血者可以向血型 A 和 AB 的受血者献血。
• 血型 B 的献血者可以向血型 B 和 AB 的受血者献血。
• 血型 AB 的献血者只能向血型 AB 的受血者献血。
• 血型 O 的献血者可以向血型 A、B、AB 和 O 的受血者献血。

在一个献血活动中有 $n$ 名志愿者，第 $i$ 名志愿者的血型由 $b_i$ 表示。注意，$b_i$ 的值只能是 A、B、AB 或 O。

当一个献血者可以向一个受血者献血，而这个受血者又可以向另一个受血者献血，以此类推，这样就形成了一个献血链条。

找出可以形成献血链条的最大人数。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据：

第一行一个整数 $n$ 表示人数。

第二行 $n$ 个用空格隔开的字符串 $b_{1\sim n}$ 表示每名志愿者的血型。

输出格式

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

4
3
A B A
2
A B
4
A B O B
5
AB A A AB A

2
1
3
5

样例解释 1

在第四组数据中，献血链可以为 A --> A --> A --> AB --> AB，长度为 5。

数据范围

对于 $30\%$ 的数据，$1\leq n,\sum n\leq 10$。

对于 $60\%$ 的数据，$1\leq n,\sum n\leq 1000$。

对于 $100\%$ 的数据，$1\leq T\leq 1000$，$1\leq n\leq 10^5$，$1\leq \sum n\leq 2\times 10^5$，$b_i\in\{A,B,AB,O\}$。