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.

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.

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

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