背景

我是可爱sjl，阳光明媚，sanchi玩拼图ᖰ⌯'▾'⌯ᖳ

描述

$2×2$，$3×3$，矩形示例，代表四个基本区块。 sanchi想玩一种由四种基本积木组成的拼图游戏，如上图所示。sanchi 有 $A,B,C,D$ 块这四种积木。现在她想用尽可能多的积木拼成一个长方形(长方形或正方形)。问题是，她最多可以用多少块积木？

拼成的长方形必须满足以下条件：

1. 任意两个相邻的基本积木必须形成凹凸结构；
2. 所形成矩形的四条边缘不得有任何突出或凹陷；
3. 与常见的益智游戏不同，本游戏中的积木没有图案，相同类型的积木被视为完全相同。

输入

第一行包含一个正整数 $T$ ($1≤T≤10^4$) 表示测试用例的数量。

对于每个测试用例，每一行都包含四个整数 $A,B,C,D$ ($0≤A,B,C,D≤10^3$) ，表示四种类型的基本模块的数量。

输出

输出 $n$ 行，每行包含一个整数，该整数表示可用于拼成矩形的给定图块的最大数量。如果无法拼成矩形，请输出 $0$ 。

样例

2
4 0 0 0
4 4 4 4

4
16

限制

1s, 1024KiB for each test case.