Review Site

题意翻译

### 题目描述 你有一个投票网站，每个用户可以投推荐票或者反对票。你的网站有两个服务器，每个服务器中的票数相互独立。 有 $n$ 个人会逐一来你的网站投票，这 $n$ 个人可以被分为三种类型： - 类型1：往所在的服务器投一张推荐票； - 类型2：往所在的服务器投一张反对票； - 类型3：若所在的服务器中反对票数量大于推荐票数量，那么他会在此投一张反对票；否则他会投一张推荐票。 你现在已经知道每位用户的类型，并且可以手动将其分配到任一服务器，求两服务器中推荐票数之和的最大值。 ### 输入格式 第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ )，表示测试数据的数量。 接下来输入 $t$ 组数据，每一组数据的第一行包含一个整数 $n$ ( $1 \le n \le 50$ )，表示用户数量。第二行包含 $n$ 个正整数 $r_1,r_2,...,r_n$ ( $1 \le r \le 3$ )，表示每一位用户的类型。 ### 输出格式 $t$ 行，每行一个正整数，表示在每组数据种你可以获得的推荐票之和的最大值。

题目描述

You are an upcoming movie director, and you have just released your first movie. You have also launched a simple review site with two buttons to press — upvote and downvote. However, the site is not so simple on the inside. There are two servers, each with its separate counts for the upvotes and the downvotes. $ n $ reviewers enter the site one by one. Each reviewer is one of the following types: - type $ 1 $ : a reviewer has watched the movie, and they like it — they press the upvote button; - type $ 2 $ : a reviewer has watched the movie, and they dislike it — they press the downvote button; - type $ 3 $ : a reviewer hasn't watched the movie — they look at the current number of upvotes and downvotes of the movie on the server they are in and decide what button to press. If there are more downvotes than upvotes, then a reviewer downvotes the movie. Otherwise, they upvote the movie. Each reviewer votes on the movie exactly once. Since you have two servers, you can actually manipulate the votes so that your movie gets as many upvotes as possible. When a reviewer enters a site, you know their type, and you can send them either to the first server or to the second one. What is the maximum total number of upvotes you can gather over both servers if you decide which server to send each reviewer to?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. Then the descriptions of $ t $ testcases follow. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 50 $ ) — the number of reviewers. The second line of each testcase contains $ n $ integers $ r_1, r_2, \dots, r_n $ ( $ 1 \le r_i \le 3 $ ) — the types of the reviewers in the same order they enter the site.

输出格式

For each testcase print a single integer — the maximum total number of upvotes you can gather over both servers if you decide which server to send each reviewer to.

输入输出样例

输入样例 #1

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

输出样例 #1

0
2
5
2

说明

In the first testcase of the example you can send the only reviewer to either of the servers — they'll downvote anyway. The movie won't receive any upvotes. In the second testcase of the example you can send all reviewers to the first server: - the first reviewer upvotes; - the second reviewer downvotes; - the last reviewer sees that the number of downvotes is not greater than the number of upvotes — upvote themselves. There are two upvotes in total. Alternatevely, you can send the first and the second reviewers to the first server and the last reviewer — to the second server: - the first reviewer upvotes on the first server; - the second reviewer downvotes on the first server; - the last reviewer sees no upvotes or downvotes on the second server — upvote themselves.