CF1511A.Review Site

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?

你是一位崭露头角的电影导演，刚刚发布了你的首部电影。你还上线了一个简单的影评网站，网站上仅有两个按钮：点赞（upvote）和点踩（downvote）。

然而，网站内部并不简单——它由两台服务器组成，每台服务器各自独立地维护该电影的点赞数与点踩数。

共有 $n$ 位影评人依次访问该网站。每位影评人属于以下三种类型之一：

• 类型 $1$：该影评人已观看电影，且喜欢这部电影——他们点击点赞按钮；
• 类型 $2$：该影评人已观看电影，但不喜欢这部电影——他们点击点踩按钮；
• 类型 $3$：该影评人尚未观看电影——他们会查看自己所进入的服务器上当前的点赞数与点踩数，并据此决定点击哪个按钮：若点踩数严格大于点赞数，则该影评人点击点踩按钮；否则，他们点击点赞按钮。

每位影评人仅对电影投票一次。

由于你拥有两台服务器，因此你实际上可以操控投票过程，使得你的电影获得尽可能多的点赞数。当一位影评人进入网站时，你已知晓其类型，并可将其分配至第一台服务器或第二台服务器。

若你能为每位影评人自主决定其进入哪一台服务器，那么两台服务器最终获得的点赞总数最多可达多少？

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.

第一行包含一个整数 $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$）—— 评审员的类型，按他们进入网站的顺序给出。

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.

对于每个测试用例，输出一个整数——即如果你决定将每位审稿人分配到哪个服务器，那么你在两个服务器上所能获得的总点赞数的最大值。

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.

在示例的第一个测试用例中，你只能将唯一一名评审员派往任一服务器——无论派往哪个服务器，该评审员都会投反对票。因此，这部电影将不会获得任何赞成票。

在示例的第二个测试用例中，你可以将所有评审员都派往第一台服务器：

• 第一名评审员投赞成票；
• 第二名评审员投反对票；
• 最后一名评审员发现当前服务器上的反对票数不大于赞成票数，于是自己投赞成票。

最终共获得两张赞成票。
另一种方案是：将第一名和第二名评审员派往第一台服务器，而将最后一名评审员派往第二台服务器：

• 第一名评审员在第一台服务器上投赞成票；
• 第二名评审员在第一台服务器上投反对票；
• 最后一名评审员在第二台服务器上未看到任何赞成票或反对票，于是自己投赞成票。