C. Function
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a function

$$$$$$ f(x)=\begin{cases} x - b + 1, & x \gt a \\ f(f(x + b)), & x \leq a \\ \end{cases} $$$$$$

and $$$t$$$ requests are given. Each request contains coefficients $$$a$$$, $$$b$$$ and variable $$$x$$$. You should calculate $$$f(x)$$$

Input

First row contains single integer $$$t$$$ — the number of tests ($$$1 \leq t \leq 10^5$$$). Following $$$t$$$ rows. $$$i$$$-th row contains 3 integers $$$a, b$$$ and $$$x$$$ ($$$1 \leq a, b, x \leq 10^{18}$$$) — function's coefficients and variable appropriately.

Output

You should output $$$t$$$ rows, each $$$i$$$-th row should contain single value — answer on $$$i$$$-th request.

Examples
Input
2
4 9 9
27 26 31
Output
1
6
Input
3
11 24 20
12 22 10
56 5 11
Output
-3
-8
53