在 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}$$$ 的团队。