#include<bits/stdc++.h>
using namespace std;

int P_th_power (int n, int m, int p) {
   // Write your code here
   vector<vector<int> > dp(n + 1, vector<int>(n + 1, -1));
   vector<int> power(n + 1);
   power[1] = 1;
   for(int i = 2; i <= n; ++i) {
       power[i] = 1;
       for(int j = 1; j <= p; ++j) {
           power[i] *= i;
       }
   }

   auto func = [&](int cur, int n, int m, auto& func) -> int {
       if(n == 0 and m == 0) {
           return 0;
       }

       if((cur > n) or (n > m) or (power[cur] > m)) {
           return 1e9;
       }
       int& val = dp[n][cur];
       if(val != -1) {
           return val;
       }
       
       // not include
       val = func(cur + 1, n, m, func);

       int cur_n = n, cur_m = m;
       auto isValid = [&](int n, int m, int val) -> bool {
           int term_a = val;
           int term_b = power[val];
           return term_a <= n and term_b <= m;
       };
       
      // number of times to include 'i' in sequence
       int times = 0;
       while(isValid(cur_n, cur_m, cur)) {
           ++times;
           cur_n -= cur;
           cur_m -= power[cur];
           val = min(val, times + func(cur + 1, cur_n, cur_m, func));
       }

       return val;
   };
   int ans = func(1, n, m, func);
   if(ans == 1e9) ans = -1;
   return ans;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for(int t_i = 0; t_i < T; t_i++)
    {
        int N;
        cin >> N;
        int M;
        cin >> M;
        int P;
        cin >> P;

        int out_;
        out_ = P_th_power(N, M, P);
        cout << out_;
        cout << "\n";
    }
}