나쁜 수

세 정수 $N$, $M$, $K$가 주어진다. $M$을 여러 개의 양의 정수의 합으로 나타내려고 하며, 다음 조건을 모두 만족해야 한다.

• 각 항(더해지는 수)은 $1$ 이상 $K$ 이하이다.
• 어떤 항도 $N$의 배수가 아니다.
• 항의 개수 역시 $N$의 배수가 아니다.

이러한 표현에서 항의 최소 개수를 구하여라.

예를 들어 $N=3$, $M=11$, $K=6$이면 $11 = 5 + 6$처럼 두 항으로 나타낼 수 있지만, $6$은 $3$의 배수이므로 이 표현은 조건을 어긴다. 항을 $3$개로 만들 수도 있으나 항의 개수 $3$ 또한 $N=3$의 배수라 허용되지 않는다. 따라서 최소 항의 개수는 $4$이며, 한 가지 예로 $11 = 4 + 4 + 2 + 1$이 있다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 각 테스트 케이스는 한 줄에 세 정수 $N$, $M$, $K$가 공백 하나로 구분되어 주어진다.

각 테스트 케이스마다 조건을 만족하는 항의 최소 개수를 한 줄에 하나씩 출력한다. 그러한 표현이 존재하지 않으면 대신 $-1$을 출력한다.

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