問題文

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

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

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

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

入力

$Q$
$A_1{B}_1{C}_1$
$⋮$
$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