题目描述

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$”（引号仅为清晰起见）。

输入数据 1

2 
3 11 6 
2 12 47

输出数据 1

4 
-1

提示

约束条件：

• $1 \leq T \leq 74$,
• $1 \leq N, M, K \leq 1000000000 (10^9)$.

来源

$2009$年东南欧区域编程竞赛