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:
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.
4 1 2 3 1 2 3 5 1 1 1 1 1 3 3 3 2
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:
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: