Problem Description

Young theoretical computer scientist Fxx designed a game for his students.

In each game, you will get three integers $X,k,t$.In each step, you can only do one of the following moves:

$1.\:X = X - i(0 <= i <= t)$.

$2.$if $k|X,X = X / k$.

Now Fxx wants you to tell him the minimum steps to make $X$ become 1.

Input

In the first line, there is an integer $T(1\leq T\leq20)$ indicating the number of test cases.

As for the following $T$ lines, each line contains three integers $X,k,t(0\leq t\leq10^6,1\leq X,k\leq10^6)$

For each text case,we assure that it's possible to make $X$ become 1。

Output

For each test case, output the answer.

2
9 2 1
11 3 3

4
3