statement.md

Description

ジョウリバーは情理乳業が発売している大人気の棒アイスです．情理乳業は「ジョウリバー交換サービス」を実施しています．ジョウリバー交換サービスとは，ジョウリバーを食べた後に残った棒（ジョウリバーの棒）を$k$本持っていくと，新しいジョウリバー1本と交換してくれるサービスです．

くまちゃんはジョウリバーが大好きな大学生で，「ジョウリバー交換サービス」を活用してなるべくたくさんのジョウリバーを食べたいと思っています．くまちゃんは初めに$n$本のジョウリバーを購入しました．くまちゃんが最終的に食べることができるジョウリバーの本数の合計の最大値を求めてください．ただし，くまちゃんが初めに持っているジョウリバーは購入した$n$本のみであり，他に未開封のジョウリバーやジョウリバーの棒を持っていることはないものとします．

Constraints

• 入力は全て整数

共通

• $n$ はくまちゃんが初めに購入したジョウリバーの本数
• $k$ は「ジョウリバー交換サービス」で1本のジョウリバーと交換するのに必要なジョウリバーの棒の本数
• $T$ はテストケースの個数

Small

• $1 \leq n \leq 100$
• $2 \leq k \leq 100$
• $T = 10$

Large

• $1 \leq n \leq 10^5$
• $2 \leq k \leq 10^5$
• $T = 100$

Input

1つの入力ファイルは複数のテストケースからなります．

入力ファイルの最初の1行目にはテストケースの個数 $T$ が記されています．

2行目以降には， $T$ 個のテストケースが記述されていて，各テストケースは次の形式で表されます．

$n$ $k$

Output

くまちゃんが最終的に食べることができるジョウリバーの本数の最大値を出力してください．

Sample Input

2
5 5
21 5

Sample Output

6
26

次の3つの値を考えてみます．

• $x$ は今持っているジョウリバーの数
• $y$ は今持っているジョウリバーの棒の数
• $z$ は今まで食べたジョウリバーの本数

1つ目のテストケース

初めに購入した5本のジョウリバーを食べ，5本のジョウリバーの棒を得ることができます．5本のジョウリバーの棒は1本のジョウリバーと交換できます．続いて，交換した1本のジョウリバーを食べ，1本のジョウリバーの棒を得ることができます．手元に残った1本のジョウリバーの棒は捨てるしかありません．よって，最終的に食べることができるジョウリバーの本数は 5 + 1 = 6本です.

$(x, y, z)$ の遷移は次のようになります．

$(5, 0, 0)$

$\to_{\mathrm{eat}} (0, 5, 5) \to_{\mathrm{trade}} (1, 0, 5)$

$\to_{\mathrm{eat}} (0, 1, 6)$

2つ目のテストケース

「ジョウリバー交換サービス」で手に入れたジョウリバーを食べた後の棒も交換に使えることに注意してください．

$(x, y, z)$ の遷移は次のようになります．

$(21, 0, 0)$

$\to_{\mathrm{eat}} (0, 21, 21) \to_{\mathrm{trade}} (4, 1, 21)$

$\to_{\mathrm{eat}} (0, 5, 25) \to_{\mathrm{trade}} (1, 0, 25)$

$\to_{\mathrm{eat}} (0, 1, 26)$