#include<bits/stdc++.h>

using namespace std;

const int inf=1e9+7;

const int maxn=1000100;

int q[maxn],f[maxn];

int x,k,t;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&x,&k,&t);
        int l=1,r=1;
        f[x]=0;
        q[1]=x;
        for(int i=x-1;i;i--)
        {
            f[i]=inf;
            while(l<=r&&q[l]>i+t)
                l++;
            if(l<=r)
                f[i]=min(f[i],f[q[l]]);
            if(1ll*i*k<=x) f[i]=min(f[i],f[i*k]);
            f[i]++;
            while(l<=r&&f[q[r]]>=f[i])
                r--;
            q[++r]=i;
        }
        printf("%d\n",f[1]);
    }
    return 0;
}