正の整数 $k$ と、$l$ から $r$ までのすべての整数を含む集合 $S$ が与えられます。 あなたは以下の2ステップの操作を任意の回数（0回でもよい）行うことができます。
- まず、集合 $S$ から、$S$ 内に $x$ の倍数が（$x$ 自身を含めて）少なくとも $k$ 個存在するような数 $x$ を選びます。
- 次に、$S$ から $x$ を取り除きます（$x$ 以外は何も取り除かれません）。
実行可能な操作回数の最大値を求めてください。
入力
各テストケースは複数のテストケースを含みます。入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。続いて各テストケースの説明が続きます。
各テストケースの唯一の行には、3つの整数 $l, r, k$ ($1 \le l \le r \le 10^9, 1 \le k \le r - l + 1$) が含まれます。これらはそれぞれ $S$ 内の最小の整数、$S$ 内の最大の整数、およびパラメータ $k$ を表します。
出力
各テストケースについて、実行可能な操作回数の最大値を1つの整数で出力してください。
入出力例
入力 1
8 3 9 2 4 9 1 7 9 2 2 10 2 154 220 2 147 294 2 998 24435 3 1 1000000000 2
出力 1
2 6 0 4 0 1 7148 500000000
注記
最初のテストケースでは、最初 $S = \{3, 4, 5, 6, 7, 8, 9\}$ です。最適な操作手順の一例は以下の通りです。
- 最初の操作で $x = 4$ を選びます。$S$ 内には 4 の倍数が 4 と 8 の 2 つ存在するためです。$S$ は $\{3, 5, 6, 7, 8, 9\}$ となります。
- 2回目の操作で $x = 3$ を選びます。$S$ 内には 3 の倍数が 3, 6, 9 の 3 つ存在するためです。$S$ は $\{5, 6, 7, 8, 9\}$ となります。
2番目のテストケースでは、最初 $S = \{4, 5, 6, 7, 8, 9\}$ です。最適な操作手順の一例は以下の通りです。
- $x = 5$ を選び、$S$ は $\{4, 6, 7, 8, 9\}$ となります。
- $x = 6$ を選び、$S$ は $\{4, 7, 8, 9\}$ となります。
- $x = 4$ を選び、$S$ は $\{7, 8, 9\}$ となります。
- $x = 8$ を選び、$S$ は $\{7, 9\}$ となります。
- $x = 7$ を選び、$S$ は $\{9\}$ となります。
- $x = 9$ を選び、$S$ は $\{\}$ となります。
3番目のテストケースでは、最初 $S = \{7, 8, 9\}$ です。$S$ 内の各 $x$ について、$x$ 以外の $x$ の倍数は $S$ 内に見つかりません。$k = 2$ であるため、操作は行えません。
4番目のテストケースでは、最初 $S = \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$ です。最適な操作手順の一例は以下の通りです。
- $x = 2$ を選び、$S$ は $\{3, 4, 5, 6, 7, 8, 9, 10\}$ となります。
- $x = 4$ を選び、$S$ は $\{3, 5, 6, 7, 8, 9, 10\}$ となります。
- $x = 3$ を選び、$S$ は $\{5, 6, 7, 8, 9, 10\}$ となります。
- $x = 5$ を選び、$S$ は $\{6, 7, 8, 9, 10\}$ となります。
5番目から8番目のテストケースについては、同様のロジックを適用することで、それぞれ出力例に示された値が得られます。