Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

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)

Hints