题目描述

小红现在有每种小写字母若干个，她想把这些字母组成一个字符串 $s$，使得字符串中任意两个相邻字母都不一样。请你帮助她求出能构造的最长字符串的长度。

思路

设所有字母数量之和为

题目内容

小红现在有每种小写字母若干个，她想把这些字母组成一个字符串$s$，使得字符串。任意两个相邻字母都不一样，请你帮助她求出最长字符串的长度。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数$T(1≤T≤1000)$,代表数据组数,每组 测试数据描述如下:

对于每一组测试数据:

每行$26$个整数,依次表示$a$~$z$的字母数量$x_i(0≤ x_i≤10^9)$。

输出描述

每组数据输出一个整数，表示满足条件的最长字符串的长度。

样例1

输入

3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5

输出

2
3
30