背景

译自 Northwestern Europe Regional Contest (NWERC) 2017 Problem H。

原题许可协议为 CC BY-SA。

题目描述

Mårten 和 Simon 喜欢玩流行桌游 Seven Wonders，并且刚刚完成了一局比赛。现在到了结算分数的时候。

Seven Wonders 中的一种得分方式来自科学。在游戏过程中，玩家可能收集到三种不同类型的科学标志：齿轮、石板和指南针。如果一名玩家拥有 $a$ 个齿轮、$b$ 个石板和 $c$ 个指南针，那么该玩家获得

分。

然而，计分会因为万能科学标志而变得复杂。对于每一个万能科学标志，玩家可以把它计作三种普通科学标志中的任意一种。例如，样例输入 #1 中的第一名玩家有 $2$ 个齿轮、$1$ 个石板、$2$ 个指南针和 $1$ 个万能科学标志，因此可以选择把三种普通科学标志的分布变为 $(3,1,2)$、$(2,2,2)$ 或 $(2,1,3)$。

这名玩家对应的可能得分分别为 $3^2+1^2+2^2+7\cdot 1=21$、$2^2+2^2+2^2+7\cdot 2=26$ 和 $2^2+1^2+3^2+7\cdot 1=21$，取决于万能科学标志如何分配。因此，这名玩家的最高得分为 $26$。

给定游戏中每名玩家拥有的各类标志数量，请计算每名玩家在最优分配万能科学标志时能够达到的最高得分。

输入格式

输入包含：

• 一行一个整数 $n$（$3 \leq n \leq 7$），表示游戏中的玩家数量。
• 接下来 $n$ 行，每行四个整数 $a,b,c,d$（$0 \leq a,b,c,d \leq 10^9$），分别表示一名玩家拥有的齿轮、石板、指南针和万能科学标志的数量。

输出格式

对于每名玩家，按照输入给出的顺序，输出该玩家可能获得的最高得分。

3
2 1 2 1
3 2 1 0
1 3 0 1

26
21
18

提示

【数据规模与约定】

对于所有数据，满足 $3 \leq n \leq 7$，$0 \leq a,b,c,d \leq 10^9$。