三带一

Problem Description

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

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

Input

输入包含 $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)$。

Output

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

Sample Input

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

Sample Output

1
9
0
3
4
5
0
253
32

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）