“—— 嗯……我想要 400 滴，但这里有 402 滴。 —— 就是 400 滴，我们从不犯错。” —— 俄罗斯动画《第三颗星球的秘密》（The Mystery of the Third Planet）

你认为经营一家餐厅很容易吗？当所有的顾客都非常挑剔时，情况就并非如此了。

你正在经营一家餐厅，每天都有很多人来找你，要求你给他们提供一些饮料。由于你的餐厅刚刚开业，你除了两个容器之外没有任何其他容器，这两个容器分别可以容纳 $a$ 滴和 $b$ 滴液体。

为了不让你的顾客等待（或者至少减少他们的等待时间），你总是需要确定在其中一个容器中精确获得 $c$ 滴液体所需的最少步数。

开始时，两个容器都是空的。以下操作被视为一步：

• 清空一个容器；
• 装满一个容器；
• 将液体从一个容器倒入另一个容器（不洒出），直到其中一个容器变满或变空。

最终，你厌倦了手动完成所有这些操作，并决定写一个程序来帮助你计算在所有这些情况下所需的最少步数。

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 10^5$)。接下来的 $T$ 行每行包含一个测试用例，由三个整数 $a$、$b$ 和 $c$ ($1 \le a, b, c \le 10^9$) 组成。

输出格式

对于每个测试用例，输出在其中一个容器中精确获得 $c$ 滴液体所需的最少步数，如果无法做到则输出 $-1$。

样例

输入样例 1

2
2 5 4
5 3 7

输出样例 1

4
-1