← 返回题目列表

Codeforces · 1511/A

A. 评论网站

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

您是一位即将上映的电影导演,并且刚刚发行了您的第一部电影。您还启动了一个简单的评论网站,其中有两个按钮可供按下 - 赞成和反对。

然而,该网站的内部并不那么简单。有两台服务器,每台服务器都有单独的赞成票和反对票计数。

$$$n$$$ 审稿人一一进入网站。每个审稿人都是以下类型之一:

- 输入 $$$1$$$:评论者观看了这部电影,并且他们喜欢它 - 他们按下了投票按钮;
- 输入 $$$2$$$:评论者看过这部电影,但他们不喜欢它 - 他们按下了否决按钮;
- 输入 $$$3$$$:评论者尚未观看该电影 - 他们会查看其所在服务器上电影当前的赞成票数和反对票数,然后决定按哪个按钮。如果反对票多于赞成票,则评论者会对该电影投反对票。否则,他们就会给这部电影投票。

每个评论者对电影只投票一次。

由于您有两台服务器,因此您实际上可以操纵投票,以便您的电影获得尽可能多的赞成票。当审阅者进入站点时,您知道他们的类型,并且可以将它们发送到第一台服务器或第二台服务器。

如果您决定将每个审阅者发送到哪个服务器,那么您可以在两台服务器上收集的最大赞成票总数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 审阅者的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 3$$$) - 审阅者的类型,与他们进入网站的顺序相同。

输出

对于每个测试用例,打印一个整数 - 如果您决定将每个审阅者发送到哪个服务器,则您可以在两台服务器上收集的最大投票总数。

示例

输入 #1

4
1
2
3
1 2 3
5
1 1 1 1 1
3
3 3 2

输出 #1

0
2
5
2

注意

在示例的第一个测试用例中,您可以将唯一的审阅者发送到任一服务器 - 他们无论如何都会投反对票。这部电影不会获得任何赞成票。

在示例的第二个测试用例中,您可以将所有审阅者发送到第一个服务器:

- 第一个审稿人点赞;
- 第二个审稿人投了反对票;
- 最后一位评论者看到反对票数不大于赞成票数 - 为自己投赞成票。

共有两票赞成。或者,您可以将第一位和第二位审阅者发送到第一台服务器,将最后一位审阅者发送到第二台服务器:

- 第一个评论者在第一台服务器上投票;
- 第二个评论者对第一个服务器投了反对票;
- 最后一位审阅者在第二台服务器上看不到赞成票或反对票 - 自己赞成票。