AT_abc290_g [ABC290G] Edge Elimination

[problemUrl]: https://atcoder.jp/contests/abc290/tasks/abc290_g $ T $ 個のテストケースについて、以下の問題を解いてください。 深さ $ D $ の完全 $ K $ 分木 ( $ 1+K+K^2+\dots+K^D $ 頂点 ) があります。 あなたの目標はこの木の辺を何本か切って、連結成分のうちいずれかを $ X $ 頂点にすることです。 目標を達成するために切るべき辺の数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ case_1 $ $ \vdots $ $ case_T $ 但し、 $ case_i $ は $ i $ 個目のテストケースである。 各テストケースは以下の形式である。 > $ D $ $ K $ $ X $

全体で $ T $ 行出力せよ。 そのうち $ i $ 行目には $ i $ 個目のテストケースに対する答えを整数として出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \le\ T\ \le\ 100 $ - $ 1\ \le\ D $ - $ 2\ \le\ K $ - $ \displaystyle\ 1\ \le\ X\ \le\ \sum_{i=0}^{D}\ K^i\ \le\ 10^{18} $