您是一位即将上映的电影导演,并且刚刚发行了您的第一部电影。您还启动了一个简单的评论网站,其中有两个按钮可供按下 - 赞成和反对。
然而,该网站的内部并不那么简单。有两台服务器,每台服务器都有单独的赞成票和反对票计数。
$$$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
注意
在示例的第一个测试用例中,您可以将唯一的审阅者发送到任一服务器 - 他们无论如何都会投反对票。这部电影不会获得任何赞成票。
在示例的第二个测试用例中,您可以将所有审阅者发送到第一个服务器:
- 第一个审稿人点赞;
- 第二个审稿人投了反对票;
- 最后一位评论者看到反对票数不大于赞成票数 - 为自己投赞成票。
共有两票赞成。或者,您可以将第一位和第二位审阅者发送到第一台服务器,将最后一位审阅者发送到第二台服务器:
- 第一个评论者在第一台服务器上投票;
- 第二个评论者对第一个服务器投了反对票;
- 最后一位审阅者在第二台服务器上看不到赞成票或反对票 - 自己赞成票。