#P12786. 三带一

    ID: 11972 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1500二分数学贪心2025“钉耙编程”中国大学生算法设计暑期联赛(3)

三带一

三带一

Problem Description

一副扑克牌有 a1a_1 张 AA,a2a_2 张 2…a102 \dots a_{10} 张 1010,a11a_{11} 张 JJ,a12a_{12} 张QQ,a13a_{13} 张 KK,我们希望打出尽可能多的三带一,问最多打出多少张。

  • 三带一指的是打出的牌需要是 AAABAAAB 类型,即四张牌中三张牌需要是相同的,剩下一张牌必须和前面的牌不一样
  • 例如 AAA2AAA2, 33383338, JJJ9JJJ9 这些都是三带一,而 66666666, 66776677, 67796779, 67896789 都不是三带一
  • 使用过的牌不能重复使用

Input

输入包含 TT 组样例; 输入第一行有一个整数 1≤T≤2×1041\leq T \leq 2\times 10^4 ,代表样例组数,每组格式如下: 每行有 1313 个整数代表数组 aa ,即 a1,a2,…,a13(0≤ai≤106)a_1,a_2,\dots,a_{13} (0 \leq a_i \leq 10^6)。

Output

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

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)