王座

题目描述

圆周上排列着 $N$ 把椅子。其中 $1$ 把是玉座（王座）。

高桥君最初坐在从玉座开始按顺时针数第 $S$ 个相邻的椅子上，并重复以下行动：

行动：从当前坐着的椅子开始，按顺时针数第 $K$ 个相邻的椅子，移动到那里坐下。

高桥君第一次能坐到玉座上是在第几次行动之后？如果永远无法坐到玉座上，则输出 -1。

请回答 $T$ 个测试用例。

输入格式

输入按以下格式从标准输入给出。第 $1$ 行如下：

$T$

接下来的 $T$ 行表示 $T$ 个测试用例，每行的格式如下：

$N$ $S$ $K$

输出格式

对每个测试用例输出答案，每个测试用例之间换行。

样例

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

2
-1
249561088
3571

在第 1 个测试用例中，有 $10$ 把椅子，高桥君最初坐在从玉座开始按顺时针数第 $4$ 个相邻的椅子上。按顺时针移动 $3$ 个相邻椅子的行动进行 $2$ 次后，就能坐到玉座上。

在第 2 个测试用例中，高桥君永远无法坐到玉座上，所以输出 -1。

数据范围

• $1 \leq T \leq 100$
• $2 \leq N \leq 10^9$
• $1 \leq S \lt N$
• $1 \leq K \leq 10^9$