黒板に整数 $N ^ M + K$ が書かれています。

Alice は黒板に書かれている整数が $N$ 未満になるまで、次の操作を行います。

操作を行う時点で黒板に書かれている整数を $x$ とする。

• $x$ が $N$ の倍数のとき、黒板に書かれている整数を消し、新たに黒板に整数 $\displaystyle \frac{x}{N}$ を書く。
• そうでないとき、黒板に書かれている整数を消し、新たに黒板に整数 $x + (N - 1)$ を書く。

Alice が操作を行う回数を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

なお、本問題の制約下において、操作を行う回数は有限回で終了することが証明できます。

Hard (100点)

• $1 \le T \le 2 \times 10^5$
• $2 \le N \le 10^{9}$
• $0 \le M \le 10^{9}$
• $0 \le K \lt N$
• 入力はすべて整数

Easy (50点)

• Hard の制約に以下の制約を追加
• $1 \le T \le 100$
• $2 \le N \le 100$
• $N ^ M + K \le 10^9$

部分点のみ解答したい場合

部分点のみを解答したい場合、問題によっては結果が TLE となるケースが大量に発生し、ジャッジに時間がかかる可能性があります。

C++の assert 関数やPythonの assert 文などを用いて、変数の値によってプログラムを強制終了させる処理を書き加えることで TLE を防ぎ、より早く結果を得ることができます。

入力は以下の形式で標準入力から与えられます。

各ケースは以下の形式で与えられます。

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースについて、答えを出力してください。