题目描述

有两个非负整数 $x$ 和 $y$。对于每一次操作，你可以选择一个数字减去1，然后另一个数字会增加1。在操作过程中，你需要确保 $x$ 和 $y$ 都是非负的。经过一些（可能为零）操作后，我们可以通过中学时学到的调整方法轻松计算出 $x^2 + y^2$ 的最大值。
现在，你有一个新的操作：给定三个非负整数 $x$、$y$ 和 $z$。对于每一次操作，你可以选择两个数字减去1，然后另一个数字会增加2。在操作过程中，你还需要确保 $x$、$y$ 和 $z$ 都是非负的。经过一些（可能为零）操作后，$x^2 + y^2 + z^2$ 的最大值是多少？

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$（$1 \leq T \leq 10^4$）——测试用例的数量。

每个测试用例的唯一一行包含三个整数 $x$、$y$、$z$（$0 \leq x, y, z \leq 10^8$）。

输出格式

对于每个测试用例，打印一个整数——经过一些（可能为零）操作后 $x^2 + y^2 + z^2$ 的最大值。

样例

2
1 1 1
2 0 0

9
4

在第一个测试案例中，$x = 1$，$y = 1$，$z = 1$。我们可以选择让 $a$，$b$ 去 $-1$，然后 $c$ 将增加 $2$。那么 $x^2 + y^2 + z^2 = 0^2 + 0^2 + 3^2 = 9$。可以验证，$x^2 + y^2 + z^2$ 的最大值是 $9$。

在第二个测试案例中，$x = 2$，$y = 0$，$z = 0$。因为我们应该确保 $x$，$y$，$z$ 都是非负的，我们不能进行操作。那么 $x^2 + y^2 + z^2 = 2^2 + 0^2 + 0^2 = 4$。