The Bad Number

You are given three integers $N$, $M$, and $K$. You want to write $M$ as a sum of positive integers subject to all of the following rules:

• Every term (summand) is between $1$ and $K$ inclusive.
• No term is a multiple of $N$.
• The number of terms is also not a multiple of $N$.

Find the minimum possible number of terms in such a representation.

For example, if $N=3$, $M=11$, and $K=6$, then $11 = 5 + 6$ uses two terms, but $6$ is a multiple of $3$, so that representation is invalid. You could instead aim for three terms, yet the count $3$ is itself a multiple of $N=3$, which is not allowed. Hence the minimum number of terms is $4$; one valid representation is $11 = 4 + 4 + 2 + 1$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $N$, $M$, and $K$ separated by single spaces.

For each test case, print the minimum possible number of terms on its own line. If no such representation exists, print $-1$ instead.

• $1 \le T \le 74$
• $1 \le N, M, K \le 10^9$