難しい和音

2 secs 1024 MB
riantkb

問題文


数列 を正整数 を用いて以下の漸化式により定義します。

ある正整数 を数列 のいくつかの要素の和として表すことを考えます。
つまり、 を満たす数列 を考えます。

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

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

制約


  • 入力は全て整数

入力


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

T
A_1 B_1 M_1
:
A_T B_T M_T

出力


行出力してください。
行目には ケース目 の答えを出力してください。

入出力例


入力例 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

Submit


Go (1.14)