一副扑克牌有 $a_1$ 张 A，$a_2$ 张 2…$a_{10}$ 张 10，$a_{11}$ 张 J，$a_{12}$ 张 Q，$a_{13}$ 张 K，我们希望打出尽可能多的三带一，问最多打出多少张。

三带一指的是打出的牌需要是 $AAA B$ 类型，即四张牌中三张牌需要是相同的，剩下一张牌必须和前面的牌不一样。
例如 $AAA2$, $3338$, $JJJ9$ 这些都是三带一，而 $6666$, $6677$, $6779$, $6789$ 都不是三带一。

使用过的牌不能重复使用。

输入格式

输入包含 $T$ 组样例；

输入第一行有一个整数 $1 \leq T \leq 2 \times 10^4$ ，代表样例组数，每组格式如下：

每行有 13 个整数代表数组 $a$，即 $a_1,a_2,\dots,a_{13}$ $(0 \leq a_i \leq 10^6)$。

输出格式

输出包括 $T$ 行，对于每一组样例你都需要输出一个答案代表最多能打出多少个三带一。

样例

输入

9
3 1 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3
2 1 2 2 1 2 1 1 0 0 0 0 0
3 4 5 0 0 0 0 0 0 0 0 0 0
1 6 9 0 0 0 0 0 0 0 0 0 0
9 1 1 9 0 0 0 0 0 0 0 0 0
100 0 0 0 0 0 0 0 0 0 0 0 0
533 109 370 0 0 0 0 0 0 0 0 0 0
4 5 6 7 8 9 10 11 12 13 14 15 16

输出

1
9
0
3
4
5
0
253
32