#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iostream>
#include <algorithm>

using namespace std;

#define rep(i,a,n) for(int i=a,_n=n;i<_n;++i)
#define per(i,a,n) for(int i=(n)-1,_a=a;i>=_a;--i)
#define all(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define ff first
#define ss second
#define siz(x) ((int)(x).size())
#define accu accumulate
#define two(x) (1<<(x))
#define twol(x) (1ll<<(x))
#define clr(a) memset(a,0,sizeof(a))
#define debug(x) cout<<#x<<" = "<<x<<endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

const int inf=0x20202020;
const int mod=1000000007;
const db eps=1e-9;
const db pi=3.1415926535897932384626;

int powmod(int a,int b){int res=1;a%=mod;for(;b;b>>=1){if(b&1)res=(ll)res*a%mod;a=(ll)a*a%mod;}return res;}

inline void rd(int &res){
    char c;res=0;
    while(c=getchar(),c<48);
    do res=res*10+(c^48);
    while(c=getchar(),c>47);
}

inline void Max(int &a,int b){if(a<b)a=b;}
inline void Min(int &a,int b){if(a>b)a=b;}
inline void add(int &a,int b){a+=b;if(a>=mod)a-=mod;}

const int M=1e6+5;
int x,k,t,dp[M],que[M];
void solve(){
    int ans=0;
    rd(x),rd(k),rd(t);
    if(!t){
        while(x>1)x/=k,ans++;
        printf("%d\n",ans);
        return;
    }
    int l=1,r=0;
    clr(dp);
    dp[1]=0;
    que[++r]=1;
    for(int i=2;i<=x;i++){
        while(l<r&&i-que[l]>t)l++;
        dp[i]=dp[que[l]]+1;
        if(i%k==0)dp[i]=min(dp[i],dp[i/k]+1);
        while(l<r&&dp[que[r]]>dp[i])r--;
        que[++r]=i;
    }
    printf("%d\n",dp[x]);
}

int main(){
    int T;rd(T);
    while(T--)solve();
    
    return 0;
}