题目描述

你有一个投票网站，每个用户可以投推荐票或者反对票。你的网站有两个服务器，每个服务器中的票数相互独立。

有 $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$ 行，每行一个正整数，表示在每组数据种你可以获得的推荐票之和的最大值。

样例

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

0
2
5
2