Scalar Product

Time limit3sMemory limit1024 MB

Summary

Given integers a, b, and R, find the maximum dot product of (a, b) with an integer point (x, y) satisfying x^2 + y^2 <= R^2.

Level: Medium7 of 10
Topics: Geometry, Math, Number theory
Solved: No attempts yet

Problem

Given integers $a$ , $b$ , and $R$ , consider the vector $(a,b)$ . Find the maximum value of the scalar product $(a,b) \cdot (x,y)$ over all integer pairs $(x,y)$ with $x^2+y^2 \le R^2$ .

Input

The first line contains one integer $T$ , the number of 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$ ).

Output

For each test case, print the maximum scalar product on a separate line.

Hint

In the first test case, there are 13 integer points $(x,y)$ with $x^2+y^2 \le R^2$ . Three of them, $(2,0)$ , $(1,-1)$ , and $(0,-2)$ , give the maximum scalar product with $(10,-10)$ . For example, $10 \times 1 + (-10) \times (-1) = 20$ .

Examples1

Example 1
Input
```
3
10 -10 2
2 3 3
5 1 3
```
Expected output
```
20
10
15
```