There are two non-negative integers x, y. For each operation, you can select a number to −1 and then another number will +1. During the operation, you should ensure that x, y are non-negative. After some (possibly zero) operations, we can easily work out the maximum value of x2 + y2 by the adjustment method we learned in middle school.
Now, you have a new operation: you are given three non-negative integers x, y, z. For each operation, you can select two numbers to −1 and then another number will +2. During the operation, you should also ensure that x, y, z are non-negative. After some (possibly zero) operations, what is the maximum value of x2 + y2 + z2 ?
输入描述:
The input consists of multiple test cases. The fifirst line contains an integer T(1 ≤ T ≤ 104 ) — the number of test cases.
The only line of each test case contains three integers x, y, z(0 ≤ x, y, z ≤ 108 ).
输出描述:
For each test case, print a single integer — the maximum value of x2 + y2 + z2 after some (possibly zero) operations.
示例1
说明
In the fifirst test case, x = 1, y = 1, z = 1. We can select a, b to −1 and then c will +2. Then
x2 + y2 + z2 = 02 + 02 + 32 = 9. Verififiably, the maximum value of x2 + y2 + z2 is 9.
In the second test case, x = 2, y = 0, z = 0. Because we should ensure that x, y, z are non-negative, we
can’t operator. Then x2 + y2 + z2 = 22 + 02 + 02 = 4.