AT_icpc2015summer_day3_e Exact Number of Drops

给定两个容量分别为 $a$ 滴水和 $b$ 滴水的杯子（开始时均为空），每步都做以下操作之一： - 将某个杯子倒空； - 将某个杯子装满； - 将一个杯子的水倒到另一个杯子，直到第一个杯子倒空或者第二个杯子装满。 求使得任意一个杯子装上恰好 $c$ 滴水的最少步数。

**本题有多组数据**。 第一行一个整数 $T (1 \leq T \leq 10^{5})$ ，表示数据组数。 对于每组数据：

对每组数据，输出一行一个整数，表示使得任意一个杯子装上恰好 $c$ 滴水的最少步数。 如果无法做到，请输出 $-1$ 。