A14230 | 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?

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.