#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
char c[10005];
int k,t;
int dp[1000005];
int que[1000005];
int main()
{
    int ty;
    cin>>ty;
    while(ty--){
        int x;
        scanf("%d%d%d",&x,&k,&t);
        dp[1]=0;
        int l1=0,r1=0;
        que[r1++]=1;
        for(int i=2;i<=x;i++){
            if(i<=t+1) dp[i]=1;
            else{
                while(l1<r1&&i-t>que[l1]){
                    l1++;
                }
                if(l1<r1)
                dp[i]=dp[que[l1]]+1;
                else dp[i]=1000000000;
                if(i%k==0){
                    dp[i]=min(dp[i],dp[i/k]+1);
                }
            }
            while(r1>l1&&dp[i]<=dp[que[r1-1]]) r1--;
            que[r1++]=i;
        }
        printf("%d\n",dp[x]);
    }
}