#define PROC "b"
#ifdef unix
#define RE "%lld"
#else
#define RE "%I64d"
#endif
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
const int MAXN = 1000504;
int q[MAXN], l, r;
int x, k, t;
int f[MAXN];
int work() {
        memset(f, -1, sizeof f);
        f[1] = 0;
        l = r = 0;
        q[r ++] = 1;
        for (int i = 2; i <= x; ++ i) {
                if (i % k == 0 && f[i / k] != -1) 
                          f[i] = f[i / k] + 1;
                if (l ^ r) {
                        int cur = f[q[l]] + 1;
                        if (f[i] == -1) f[i] = cur;
                        else f[i] = min(f[i], cur);
                }
                if (f[i] != -1) {
                        while (l != r && f[q[r - 1]] >= f[i]) r --;
                        q[r ++] = i;
                        while (l != r && q[l] < i + 1 - t) ++ l;
                }
        }
        return f[x];
}
int main() {
        int T;
        scanf("%d", &T);
        while (T -- ) {
                scanf("%d%d%d", &x, &k, &t);
                printf("%d\n", work());
        }
        return 0;
}