Consider the following problem.

We have a perfect \(K\)-ary tree of depth \(D\).
First, choose a vertex \(v\) at depth \(h\). If it has a parent, cut the edge towards it, discarding the connected component without \(v\).
Then, repeatedly cut an edge and discard the connected component without \(v\). Your objective is that the connected components containing \(v\) has \(X\) vertices.
How many edges should be cut to achieve the objective? Here, if it is unachievable, let the answer \(\infty\).

Simply put, we choose a vertex \(v\), and try to make the connected component containing \(v\) be “rooted” at \(v\) so that it has \(X\) vertices.
Once we solve this problem for all vertex \(v\), or equivalently all integers \(h\) such that \(0 \le h \le D\), the problem is solved.

To come to the conclusion, this problem can be solved by the following procedure.

• The first cut yields a perfect \(K\)-ary tree of depth \((D-h)\).
• If less than \(X\) vertices remain, the answer is \(\infty\).
• Otherwise, it can be solved greedily.
  • For each \(i=D-h-1,D-h-2,\dots,0\), remove a perfect \(K\)-ary subtree of depth \(i\) as many times as possible (you may remove it if and only if at least \(X\) vertices remain).

We now justify this greedy algorithm.
We denote by \(V_i\) the number of vertices in a perfect \(K\)-ary tree of depth \(i\). Here, \(V_i=1+K^1+\dots+K^{i}=\frac{K^{i+1}-1}{K-1}\).

Step 1: Proving that the greedy construction is optimal when representing \(V_{D-h}-X\) by the minimum number of \(V_i\)’s

This problem is equivalent to the following problem: “you have infinite number of \(V_0\)-yen coins, \(V_1\)-yen coins, \(\dots\), and \(V_{D-h-1}\)-yen coins. At least how many coins do you need to pay \((V_{D-h}-X)\) yen?” There is a research on whether this problem can be solved with the greedy algorithm. For example, searching “コイン 貪欲法” (coins greedy algorithm) yields an article (Japanese) on it. According to the article, the greedy algorithm is valid in the following situation:

Let \(a_1,a_2,\dots,a_n\) be the value of the coins in ascending order. Then, an integer pair \((p,q)\) such that \(a_{j+1}=pa_j−q\) and \(0 \le q < a_j\) is uniquely determined for all \(j\).
For that \((p, q)\), if \(H(q) \le p−1\) holds for all \(j\), the greedy algorithm of choosing the maximum applicable coin is valid.
Here, \(H(x)\) denotes the minimum number, obtained by the greedy algorithm, of coins required to pay \(x\).

Now we try to apply this condition to this problem.
Since, \(V_1 = (K+1) \times V_0- 0, H(0)=0 \le (K+1)\), it holds between \(V_0\) and \(V_1\). For \(j \ge 1\), comparison between \(V_{j}\) and \(V_{j+1}\) can be deformed as \(V_{j+1}=\frac{K^{j+2}-1}{K-1} = (K+1) \times \frac{K^{j+1}-1}{K-1} - \frac{K^{j+1}-K}{K-1}\), so \(p=(K+1)\) and \(q=\frac{K^{j+1}-K}{K-1}=K \times \frac{K^{j}-1}{K-1}\).
Since \(H(K \times \frac{K^{j}-1}{K-1}) = H(K \times V_{j-1}) = K \le (K+1)-1\), the greedy algorithm has been proven to be valid.

Step 2: Proving that the removal of subtrees corresponding to step 1 is actually possible

If less than or equal to \(K\) vertices need to be removed, it is obvious; just tear off the leaves.
If \(K+1\) or more vertices need to be removed, we need to remove a whole subtree of depth \(2\). Then we may consume one subtree of depth \(2\) to remove up to \(K(K+1)\) vertices by using up to \(K\) subtrees of depth \(1\).
If \(K(K+1)+1 = K^2+K+1\) vertices need to be removed, we need to remove a whole subtree of depth \(2\). Then we may consume one subtree of depth \(3\) to remove up to \(K(K^2+K+1)\) vertices by using up to \(K\) subtrees of depth \(2\).
When it comes to removing \(K(K^2+K+1)+1 = K^3+K^2+K+1\) vertices, a whole subtree of depth \(3\) will be removed.\(\dots\)

Repeating this step completes the proof of this step..

The complexity of this solution is \(O(D^2)\). Since \(D \le 60\), it is fast enough even with \(100\) cases.

This solution is easy to come up with by observing smaller cases, but the proof is rather complicated. Editorial of another solution

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

long long greedy(long long x,long long k,long long p,vector<long long> &a){
  if(x==0){return 0;}
  if(x<0){return 8e18;}
  long long res=0;
  for(long long i=p;i>=0;i--){
    long long use=(x/a[i]);
    res+=use;
    x-=use*a[i];
  }
  if(x>0){return 8e18;}
  return res;
}

int main(){
  int tc;
  cin >> tc;
  while(tc>0){
    tc--;
    long long d,k,x;
    cin >> d >> k >> x;

    long long res=8e18;
    vector<long long> a(d+1);
    a[0]=1;
    for(long long i=1;i<=d;i++){a[i]=a[i-1]*k+1;}

    for(long long h=d;h>=0;h--){
      long long rem=a[h]-x;
      if(0<=rem){
        long long up=1;
        if(h==d){up=0;}
        res=min(res,up+greedy(rem,k,h-1,a));
      }
    }
    cout << res << "\n";
  }
  return 0;
}