Pku3902 The Bad Number

John 和 Brus 认为数 $N$ 是一个非常糟糕的数，因此他们每时每刻、在任何地方都想避开它。

现在他们想把数 $M$ 表示成若干个正整数之和，其中每个加数都不超过 $K$ 。但是不要忘了那个糟糕的数 $N$ ：每个加数都不能是 $N$ 的倍数，而且加数的个数也不能是 $N$ 的倍数。

你的任务是求出这样的表示中，加数个数的最小可能值。

例如，若 $N=3$ 、 $M=11$ 、 $K=6$ ，我们可以把 $M$ 写成 $5+6$ ，但由于 $6$ 是 $3$ 的倍数，所以至少需要 $3$ 个加数；而 $N=3$ 时加数个数又不能是 $3$ ，因此答案是 $4$ ，一种可行的表示是 $11=4+4+2+1$ 。

输入格式

第一行是一个整数 $T$ ，表示测试数据组数。

接下来每组数据一行，包含三个用空格分隔的整数 $N$ 、 $M$ 和 $K$ 。

对于每组数据，输出一行一个整数，表示满足上述要求的最小加数个数。如果无法做到，则输出 -1。

2
3 11 6
2 12 47

4
-1

第一组数据即题目描述中的例子，答案为 $4$ ，例如 $11=4+4+2+1$ 。

第二组数据中 $N=2$ ，每个加数都必须是奇数，加数个数 $P$ 也必须是奇数；而奇数个奇数之和仍为奇数，不可能等于 $12$ ，因此无解，输出 -1。

本题为 PKU 3902 试题「The Bad Number」，题面与测试数据整理自 BZOJ 2488。

2
3 11 6
2 12 47

4
-1