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.
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。
For each test case, output the answer.