问题 E: 美味佳肴

老师对于同学们建设美丽校园的工作十分满意，因此特意在食堂四楼包下包间请同学们一起吃饭。  
小明一心干饭，但由于老师同时在场，转桌夹菜时便收敛了些。
已知圆桌上共有 $N$ 个位置，现在在圆桌的第 $0$ 位处有一盘小明很想吃的美味佳肴，小明坐在圆桌上顺时针方向上的第 $S$ 位，每次小明转桌可使得菜肴逆时针移动 $K$ 位（即从第 $i$ 位移动到第 $(i-K+N)$ $mod$ $N$ 位，其中 $mod$ 为取余操作），问小明最少需要转几次桌才可以使得美味佳肴移动到自己面前，能够优雅地夹到想吃的菜？如果无论怎么转桌小明都无法使得美味佳肴到达自己面前，则输出 $-1$

输入包括 $T+1$ 行，
第一行包括一个正整数 $T$ ，表示共有 $T$ 组数据 $(1 \leq T \leq 100)$ 
第 $2$ 到 $T+1$ 行每行包括三个正整数依次为 $N$ ， $S$ ， $K$ $(2 \leq N \leq 10^9,1 \leq S < N ,1 \leq K \leq 10^9)$ 

输出共 $T$ 行，
每行包括一个整数表示每组测试数据对应的答案

4
10 4 3
1000 11 2
998244353 897581057 595591169
10000 6 14

2
-1
249561088
3571