#include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int dis[maxn];

 int d[maxn];

 #define inf 0x3f3f3f3f

 int main()

 {

     int t;

     cin>>t;

     while(t--) {

         int x,k,t;

         cin>>x>>k>>t;

         int l,r;

         l = r = ;

         dis[] = ;

         d[] = ;

         for(int j=;j<=x;j++) {

             dis[j] = inf;

             while(l<=r&&d[l]<j-t) l++;

             if(l<=r) dis[j] = dis[d[l]] + ;

             if(j%k==) dis[j] = min(dis[j],dis[j/k]+);

             while(l<=r&&dis[d[r]]>=dis[j]) r--;

             d[++r] = j;

         }

         printf("%d\n",dis[x]);

     }

     return ;

 }