B. Changing Change
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp is a cashier at Hudson River Trader Joe's (HRTJ). HRTJ has some weirdly valued coins, and the available coin values can change from day to day!

On a day with parameters $$$b$$$ and $$$k$$$, HRTJ has coins worth $$$b^0,b^1,\ldots,b^k$$$ cents. Magikarp has an unlimited number of coins of each of these values. He must give a customer exactly $$$x$$$ cents in change.

For each of $$$t$$$ days, find the minimum number of coins Magikarp needs. Each day is independent.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of days.

Each of the next $$$t$$$ lines contains three integers $$$b$$$, $$$k$$$, and $$$x$$$ ($$$2 \le b \le 10^9$$$, $$$0 \le k \le 29$$$, $$$1 \le x \le 10^9$$$) — the base of the coin values, the largest exponent, and the amount of change in cents for that day, respectively.

It is guaranteed that $$$b^k \le 10^9$$$ for each day.

Output

For each day, output a single integer on its own line — the minimum number of coins needed to give exactly $$$x$$$ cents in change.

Examples
Input
1
3 3 35
Output
5
Input
5
10 2 1234
2 0 1000000000
1000000000 1 1
2 29 536870912
10 9 1000000000
Output
19
1000000000
1
1
1
Input
3
2 3 20
5 1 20
10 0 20
Output
3
4
20
Input
1
1000000000 1 999999999
Output
999999999
Note

In the first sample, the coin values are $$$1$$$, $$$3$$$, $$$9$$$, and $$$27$$$. Magikarp can give $$$35$$$ cents using five coins: $$$27+3+3+1+1=35$$$.

In the second sample:

  • On the first day, the coin values are $$$1$$$, $$$10$$$, and $$$100$$$. Magikarp needs twelve $$$100$$$-cent coins, three $$$10$$$-cent coins, and four $$$1$$$-cent coins, for a total of $$$19$$$ coins.
  • On the second day, $$$k=0$$$, so only $$$1$$$-cent coins are available. Magikarp needs $$$10^9$$$ coins.
  • On the third day, the change is $$$1$$$ cent, so one $$$1$$$-cent coin is enough.
  • On the fourth day, one coin worth $$$2^{29}$$$ cents is enough.
  • On the fifth day, one coin worth $$$10^9$$$ cents is enough.

In the third sample, the change is $$$20$$$ cents on every day, but the coin values change. Magikarp can use $$$8+8+4$$$ on the first day and $$$5+5+5+5$$$ on the second day. On the third day, he must use twenty $$$1$$$-cent coins.

In the fourth sample, the only coin values are $$$1$$$ and $$$10^9$$$. The larger coin exceeds the required change, so Magikarp must use only $$$1$$$-cent coins.