### 问题描述 在活体器官捐赠中，以下血型是相互兼容的： - 血型 A 的捐赠者可以向血型 A 和血型 AB 的接受者捐赠。 - 血型 B 的捐赠者可以向血型 B 和血型 AB 的接受者捐赠。 - 血型 AB 的捐赠者只能向血型 AB 的接受者捐赠。 - 血型 O 的捐赠者可以向所有血型的接受者捐赠。 现在，医院里有 $N$ 名患者，第 $i$ 名患者的血型为 $B_i$。注意，$B_i$ 的值只能是 A，B，AB 或 O。 当一个捐赠者可以向一个接受者捐赠血液，而该接受者又可以向另一个接受者捐赠血液，依此类推，我们称这样的患者序列构成了一个链。 你的任务是找出可以构成血液输血链的最大人数。 ### 输入格式 第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例包含两行： - 第一行输入一个整数 $N$，表示患者的数量。 - 第二行输入 $N$ 个字符串，分别是 $B_1$，$B_2$，...，$B_N$，表示每名患者的血型。 ### 输出格式 对于每个测试用例，输出一个整数，表示可以构成血液输血链的最大人数。 ### 样例输入 ```markdown 4 3 A B A 2 A B 4 A B O B 5 AB A A AB A ``` ### 样例输出 ```markdown 2 1 3 5 ``` ### 说明 样例中的第一个测试用例：这里有 $3$ 名患者，他们的血型为 A，B 和 A。可以形成的链为第 $1$ 名患者到第 $3$ 名患者，因此，链的长度为 $2$。 样例中的第二个测试用例：这里有 $2$ 名患者，他们的血型为 A 和 B。两名患者的血型不兼容，因此，链的长度为 $1$。 ### 评测数据范围 $1 \leq T \leq 1000$。 $1 \leq N \leq 10^5$。 $B_i \in \textbraceleft A, B, AB, O\textbraceright $。 所有测试用例中 $N$ 的和不超过 $2 \times 10^5$。