問題文

くる君は最初$0$枚のクッキーを持っています。くる君はクッキーを$A$枚ちょうどにしたいです。
クッキーを増やすには次の$2$種類の操作があります。

　・$B$円を支払う。$1$以上$C$未満の数字$i$を一つ選び、クッキーを購入する。クッキーの枚数が$i$増える。
　・$B$円を支払う。クッキーを叩き割る許可を得ることができ、クッキーの枚数が$C$倍になる。

上記の操作は好きな順番で好きな回数行うことができます。
くる君は出来るだけ少ないお金でクッキーを$A$枚ちょうどにしたいです。その最小コストを求めてください。
クッキーを$A$枚ちょうどにできないときは$-1$を出力してください。

なお入力は$Q$クエリ与えられるので、それぞれに対して答えを求めてください。

入力

$Q$
$A_1\ B_1\ C_1$
$\vdots$
$A_Q\ B_Q\ C_Q$

入力は全て整数である
$1 \le Q \le 20$
$1 \le A_i,B_i,C_i \le 10^9\ (1 \le i \le Q)$

出力

$Q$行出力してください。
$A_i,B_i,C_i$をそれぞれ問題文中の$A,B,C$としてクエリに答えてください。
1クエリごとに改行してください。

サンプル

1
7 1 3

3

1
133 2 5

12

2
12345789 987654321 57
12 2 3

7901234568
6