So Many Dice

問題文

$1$ から $N$ までの目が書かれた $N$ 面サイコロがある。ここで、サイコロのどの目が出る確率も同様に確からしいものとする。このサイコロを $K$ 回振った際に、 $A$ 以下の目が $x$ 回出る確率を $P(x)$ とおく。$P(x)$ が最大となるような $x$ のうち、最も小さいものを求めよ。$T$ 個のテストケースが与えられるので、それぞれのケースについて答えを出力せよ。

制約

• $1 \leq T \leq 2 \times 10^{5}$
• $1 \leq N,K \leq 10^{9}$
• $1 \leq A \leq N$

入力

入力はすべて整数である。

まず、初めにテストケースの個数 $T$ が与えられる。その後、 $T$ 行に渡って各テストケースの内容が与えられる。

T
testcase_1
testcase_2
...
testcase_T

各テストケースは以下のようにして与えられる。

N K A

出力

それぞれのテストケースについて、答えをそれぞれ1行づつ出力せよ。

サンプル

1
6 2 3

1

6面サイコロを1回振って3以下の目が出る確率は $1/2$ です。よってこのサイコロを2回振ったときに3以下の目が出る回数とその確率は次の通りです。

• 0回 : ${}_2C_{0} \times 1/2 \times 1/2 = 1/4$
• 1回 : ${}_2C_{1} \times 1/2 \times 1/2 = 1/2$
• 2回 : ${}_2C_{2} \times 1/2 \times 1/2 = 1/4$

よって3以下の目が1回出る確率が最も大きいので、1を出力します。

2
2 1 1
2 10 2

0
10

1つ目のテストケースについて、2面サイコロを1回振ったときに1の目が0回出る確率と1回出る確率は等しいです。この場合、1の目が出る回数が少ない方を採用するため、0を出力します。

4
23 194 11
510 647 259
666 333 222
8282828 210201 2938281

93
329
111
74567