← 返回题目列表

Codeforces · 1703/B

B. ICPC 气球

中文机器翻译题面 查看原题

在 ICPC 竞赛中,气球的分配方式如下:

- 每当一个团队解决问题时,该团队就会得到一个气球。
- 第一个解决问题的团队会获得一个额外的气球。

确定各队收到的气球总数。请注意,有些问题可能没有一个团队能够解决。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) — 字符串的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由大写英文字母组成,表示解决问题的顺序。

输出

对于每个测试用例,输出一个整数 - 团队收到的气球总数。

示例

输入 #1

6
3
ABA
1
A
3
ORZ
5
BAAAA
4
BKPT
10
CODEFORCES

输出 #1

5
2
6
7
8
17

注意

在第一个测试用例中,给出了 $$$5$$$ 气球:

- 问题 $$$\textsf{A}$$$ 已解决。该团队收到 $$$2$$$ 气球:一个是因为他们解决了问题,另一个是因为他们是第一个解决问题 $$$\textsf{A}$$$ 的团队。
- 问题 $$$\textsf{B}$$$ 已解决。该团队收到 $$$2$$$ 气球:一个是因为他们解决了问题,另一个是因为他们是第一个解决问题 $$$\textsf{B}$$$ 的团队。
- 问题 $$$\textsf{A}$$$ 已解决。该团队只收到 $$$1$$$ 气球,因为他们解决了问题。请注意,他们没有获得额外的气球,因为他们不是第一个解决问题 $$$\textsf{A}$$$ 的团队。

在第二个测试用例中,只解决了一个问题。解决问题的团队会收到 $$$2$$$ 气球:一个是因为他们解决了问题,另一个是因为他们是第一个解决问题 $$$\textsf{A}$$$ 的团队。