Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Optimal Walk

By humayan7711 · Limits 2s, 512 MB

IIKI is in great trouble. In the game called BIIKI, The Hero CIIKI gets power MM for per kilometer distance covered in the X-direction and power NN for per kilometer distance covered in the Y-direction. Initially, CIIKI is in (0,0) coordinate and can go any direction but not in any negative direction.

More formaly, he can go from (x, y) to (a, b) if and only if xa and ybx \leq a\ and\ y \leq b.

You are given the distance DD which will be covered by CIIKI.
What is the maximum amount of power CIIKI will get if IIKI plays optimally?

Input

The first line contains one integer TT ( 1T51051\leqslant T \leqslant 5*10^5 ) — the number of test cases. Each test case is represented by one line containing three integers MM, NN, and DD.

Constraints

  • $-10^9\leqslant$ $M, N \leqslant 10^9$
  • $0\leqslant$ $D \leqslant 10^9$

Output

Print T numbers the maximum amount of power CIIKI can achieve.
Your answer will be considered correct if its absolute or relative error doesn't exceed 10610^{-6}.
Formally, if your answer is aa and judge's answer is bb then your answer will be considered correct if abmax(1,b)106\frac {|a-b|} {max(1, |b|)} \leq 10^{-6}.

Sample

InputOutput
3
5 0 4
-1 2 3
-3 -4 3
20
6
-9

    Discussion

    Statistics


    21% Solution Ratio

    jamil314Earliest, Aug '20

    nihalshahriaFastest, 0.4s

    nihalshahriaLightest, 6.2 MB

    MansurbekShortest, 249B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.