Problem Statement

Kuru-kun initially has $0$ cookies. He wants to have exactly $A$ cookies.
There are the following $2$ types of operations for increasing the number of cookies.

　・Pay $B$ yen. Choose one number $i$ that is at least $1$ and less than $C$, and buy cookies. The number of cookies increases by $i$.
　・Pay $B$ yen. You obtain permission to smash the cookies, and the number of cookies is multiplied by $C$.

The above operations can be performed in any order and any number of times.
Kuru-kun wants to have exactly $A$ cookies using as little money as possible. Find the minimum cost.
If it is impossible to have exactly $A$ cookies, output $-1$.

The input is given as $Q$ queries, so find the answer for each of them.

Input

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

All inputs are integers.
$1 \le Q \le 20$
$1 \le A_i,B_i,C_i \le 10^9\ (1 \le i \le Q)$

Output

Output $Q$ lines.
Answer each query, with $A_i,B_i,C_i$ being $A,B,C$ in the problem statement, respectively.
Print a newline after each query.

Sample

1
7 1 3

3

1
133 2 5

12

2
12345789 987654321 57
12 2 3

7901234568
6