難しい和音

問題文

数列 $(F_n)_{n=0, 1, \dots}$ を正整数 $A, B$ を用いて以下の漸化式により定義します。

ある正整数 $M$ を数列 $(F_n)$ のいくつかの要素の和として表すことを考えます。
つまり、$M = F_{p_1} + F_{p_2} + \dots + F_{p_k} \ ( 0 \le p_1 \lt p_2 \lt \dots \lt p_k )$ を満たす数列 $p$ を考えます。

このとき、数列 $p$ の要素数 $k$ としてありうる最大値を求めてください。
なお、数列 $p$ としてありうるものが存在しない場合は代わりに -1 と出力してください。

この問題では一つの入力につきテストケースが $T$ 個与えられます。

制約

• 入力は全て整数
• $1 \le T \le 50{,}000$
• $1 \le A, B, M \le 10^{16}$

入力

入力は以下の形式で与えられます。

出力

$T$ 行出力してください。
$i \ (1 \le i \le T)$ 行目には $i$ ケース目 $(A_i, B_i, M_i)$ の答えを出力してください。

入出力例

入力例 1

9
1 1 2
1 1 9
5 1 21
2 1 200
1 2 200
12 3 456789
2 2 99
10 1 2
1 1 10000000000000000

出力例 1

2
4
3
6
7
15
-1
-1
52