시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB233315.789%

문제

Given vector $(a,b)$ (where $a$ and $b$ are integers) and integer $R$. Find the maximum value of the scalar product $(a,b) \cdot (x,y)$, where both $x$ and $y$ are integer, and $x^2+y^2 \le R^2$.

입력

First line of the input contains one integer $T$ --- the number of the test cases ($1 \le T \le 1\,000$). Each of the following $T$ lines contains three integers $a$, $b$ and $R$ ($-10^9 \le a,b \le 10^9$, $1 \le R \le 10^9$).

출력

For each test case, print in the separate string one integer --- the maximal scalar product.

예제 입력 1

3
10 -10 2
2 3 3
5 1 3

예제 출력 1

20
10
15

노트

For the first test case in the sample, we have 13 integer points $(x,y)$ such as $x^2+y^2 \le R^2$. Between those 13 points we have three points $(2,0)$, $(1,-1)$, $(0,-2)$ with the scalar prodct on $(10,-10)$ reaches the maximum, for example, $10 \times 1 + (-10) \times (-1) = 20$.