题目描述

「未来」号飞船有一个立方体引擎， 长宽高分别为 $ x - 1, y - 1, z - 1 $，即有 $ xyz $ 个节点， 现在这个引擎没有能量了， 有一种机器人， 它可以选一个节点出发， 每次走到相邻的节点并把经过的这条边充上能， 每次移动需要耗费 $ 1 $ 的能量， 只有引擎上所有的边都被充上了能， 引擎才可以启动， 现在船长想知道， 用这个机器人给引擎充能最少需要耗费多少能量。

输入格式

第一行一个正整数 $ t $ 表示测试数据组数。
接下来 $ t $ 行每行三个正整数 x y z 表示一组询问。

输出格式

对每个询问输出一行表示答案。

样例

input

3
1 1 2
1 2 2
233 666 999

output

1
4
465060895

数据范围与提示

$ t, x, y, z \leq 100000 $