#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define N 1100000
using namespace std;
int f[N],n,m,k,p[N],head,tail,inf=N;
int main()
{
    int z;scanf("%d",&z);
    while(z--)
    {
        scanf("%d%d%d",&n,&k,&m);
        f[1]=0;
        p[1]=1;head=tail=1;
        for(int i=2;i<=n;i++)
        {
            f[i]=inf;
            if(i%k==0) f[i]=f[i/k]+1;
            while(head<=tail && i-p[head]>m) head++;
            f[i]=min(f[i],f[p[head]]+1);
            while(head<=tail && f[i]<f[p[tail]]) tail--;
            p[++tail]=i;
        }
        printf("%d\n",f[n]);
    }
    return 0;
}