A - Alternating Function

Time limit: 1 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

Let $h$ be a function defined on the set of all positive integers such that $h(n)=(-1)^n \cdot n \cdot p + k$, $(1 \le p,k \le 10^{17})$.


Find the minimum positive integer $x$ such that $h(x) \ge m$, $(1 \le m \le 10^{17})$. It can be proven that such $x$ exists.

Input

The first line of the input contains a single integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases.


The following $t$ lines contain three spaced separated integers $p$, $k$, $m$, describing each test case.

Output

For each test case, print a line with one integer, the minimum positive integer $x$ such that $h(x) \ge m$.

Sample test(s)

Input
3 1 3 200 99 1 100 1 70 90
Output
198 2 20
Input
2 567 23 900000000 7 3 100000000000000000
Output
1587302 14285714285714286

Hints