problem_statement.md

Minimum Forbidden Jumps

Time Limit: 1 seconds

Memory Limit: 32 MB

A robot starts at gate $0$ and must reach gate $x$ on a straight line of numbered gates.

In one move, it can advance by an integer distance $a$ such that:

• $1 \le a \le m$
• $a$ is not divisible by $k$ (i.e., $a \not\equiv 0 \pmod{k}$)

For each test case, determine the minimum number of moves required to land exactly on gate $x$.

It is guaranteed that reaching $x$ is always possible.

Input Format:-

The first line contains an integer $t$ — the number of test cases.
Each of the next $t$ lines contains three integers $x, k, m$.

Output Format:-

For each test case, print one integer — the minimum number of moves needed to reach exactly $x$.

Constraints:-

• $1 \le t \le 1000$
• $1 \le x \le 10^{18}$
• $2 \le k \le 10^9$
• $1 \le m \le 10^9$ Examples:-
• Input:

1
7 7 8

• Output:

2

• Input:

1
60 2 3

• Output:

20

Note:-
In the first example, $x=7$, $k=7$, $m=8$. The jump length $7$ is forbidden because $7 \equiv 0 \pmod{7}$, but $1$ and $6$ are allowed. One optimal way is to do $6+1=7$, so the minimum number of moves is $2$.

In the first example, $x=60$, $k=2$, $m=3$. Allowed jump lengths are $1$ and $3$ (since $2$ is divisible by $2$ and forbidden). To minimize moves, use the maximum allowed jump repeatedly: $$60 = 20 \cdot 3,$$ so the robot reaches gate $60$ in $20$ moves.