#include<iostream>
using namespace std;
#define INF 2147483640
#define N 1000010
struct data{long long t,c;}q[N];
long long ttt,x,k,t,i,h,tt,f[N];
inline int rd(){int t;scanf("%d",&t);return t;}
int main(){
    ttt=rd();
    while (ttt--){
        x=rd(),k=rd(),tt=rd();
        for (i=2,q[h=t=1]=(data){1,0};i<=x;i++){
            f[i]=i%k==0&&k!=1?f[i/k]+1:INF;
            while (h<=t&&q[h].t<i-tt) h++;
            if (h<=t) f[i]=min(f[i],q[h].c+1);
            while (h<=t&&q[t].c>=f[i]) t--;
            q[++t]=(data){i,f[i]};
        }
        cout<<f[x]<<"\n";
    }
    return 0;
}