#include <cstdio>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define getmid(l,r) ((l) + ((r) - (l)) / 2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define MP(a,b) make_pair(a,b)
#define PB push_back

typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;

int T,x,k,t;
int dp[1000010];
pair<int,int> Q[1000010];
int head,rear;

int Solve(int x){
    head = 1;
    rear = 0;
    Q[++rear] = MP(0,x);
    memset(dp,0x3f,sizeof(dp));
    dp[x] = 0;
    for(int i = x - 1; i >= 1; --i){
        while(head <= rear && Q[head].second - t > i){
            head++;
        }
        if(head <= rear) dp[i] = Q[head].first;
        if(1ll * i * k <= x) dp[i] = min(dp[i],dp[i * k]);
        dp[i]++;
        while(head <= rear && Q[rear].first >= dp[i]){
            rear--;
        }
        Q[++rear] = MP(dp[i],i);
    }
    return dp[1];
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&x,&k,&t);
        if(x == 1){
            printf("0\n");
            continue;
        }
        printf("%d\n",Solve(x));
    }
    return 0;
}