青年理论计算机科学家Fxx给的学生设计了一款数字游戏。 一开始你将会得到一个数$\:X$，每次游戏将给定两个参数$\:k,t$, 任意时刻你可以对你的数执行下面两个步骤之一： $1.\:X = X - i(1 <= i <= t)$。 $2.\:$若$\:X\:$为$\:k\:$的倍数，$X = X / k$。 现在Fxx想要你告诉他最少的运行步骤，使$\:X\:$变成$\:1$。
第一行一个整数$\:T(1\leq T\leq20)\:$表示数据组数。 接下来$\:T\:$行，每行三个数$\:X,k,t(0\leq t\leq10^6,1\leq X,k\leq10^6)$ 数据保证有解。
输出共$\:T\:$行。 每行一个整数表示答案。
2 9 2 1 11 3 3
4 3