Viktor Mikhailovich Polesov 是一位真正的知识分子代表，他聪明且思维敏捷。他最近了解到，力的功是力向量与位移向量的点积。自然地，他想要最大化功，以免浪费任何能量。他所要做的就是选择移动到哪里。

可以从点 $(0, 0)$ 移动到圆 $x^2 + y^2 \le R^2$ 内的任意整点。已知力向量在各处相同，其坐标为 $(a, b)$。请找出 Polesov 所好奇的最大功。

输入格式

输入文件的第一行包含一个整数 $T$ —— 测试用例的数量 ($1 \le T \le 1000$)。 接下来有 $T$ 行，每行包含三个整数 $a, b$ —— 力向量的坐标，以及 $R$ —— 圆的半径 ($-10^9 \le a, b \le 10^9, 1 \le R \le 10^9$)。

输出格式

对于每个测试用例，输出一个整数 —— 最大功。

样例

输入 1

3
10 -10 2
2 3 3
5 1 3

输出 1

20
10
15

说明

在第一个测试用例中，圆心在原点且半径为 $2$ 的圆包含 $13$ 个整点。对于点 $(2, 0), (1, -1), (0, -2)$，与力向量 $(10, -10)$ 的点积最大。例如，$10 \times 1 + (-10) \times (-1) = 20$。