#include<cstdio>
#include<algorithm>
using namespace std;
int T,n,k,t,p1,p2,f[1000010],q[1000010];
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&k,&t);
        if (t == 0)
        {
            int ans = 0;
            while (n > 1) n /= k, ans++;
            printf("%d\n", ans);
            continue;
        }
        f[1]=0;p1=p2=1;q[1]=1;
        for (int i=2;i<=n;i++)
        {
            while (i-q[p1]>t) p1++;
            f[i]=f[q[p1]]+1;
            if (i%k==0) f[i]=min(f[i],f[i/k]+1);
            while (p1<=p2&&f[q[p2]]>=f[i]) p2--;
            q[++p2]=i;
        }
        printf("%d\n",f[n]);
    }
}