フランクはカードゲームが好きで、週末は友達の家でゲームパーティーに参加しています。彼らがゲームに使うカードは M 枚からなり、それぞれ 1 から M までの数字が重複しないように書かれています。フランクはパーティーで友人が使っている自動カードシャッフル装置と同じものを持っていて、どのように動作するか理解しています。その装置はカードの山を C 回カットすることでシャッフルを行います。i 回目のカットではカードの山の上から A_i 番目から B_i 枚、つまり A_i 番目から A_i + B_i - 1 番目のカードがそのままの順番で山の上に移動します。</p>

ある日、いつも使っているカードが汚れたため、新しいカードを使うことになりました。新しいカードは上から順番に 1 から M まで並んだ状態でそのままシャッフル装置にかけられました。フランクはシャッフル装置の性質を利用し、シャッフル後に上から W 番目にあるカードが何かを知ろうとしています。

입력 형식

最初の行はテストケースの個数 T を表す正の整数です。続いて、各テストケースが次のようなフォーマットで与えられます。</p>

M C W
A1 B1
...
AC BC

1行目では、1 つのスペースで区切られた 3 つの整数 M, C, W が与えられます。ここで M はカードの枚数 、C はカットの回数、W は知りたいカードの位置です。 続く C 行の各行では、1 つのスペースで区切られた 2 つの整数 A_i, B_i が与えられます。 ここで A_i, B_i はカットの操作で、i 回目の操作で上から A_i 番目から B_i 枚のカードを山の上に移動させることを意味しています。

制約

• 1 ≤ T ≤ 200
• 1 ≤ C ≤ 100
• 1 ≤ W ≤ M
• 1 ≤ A_i ≤ M
• 1 ≤ B_i ≤ M
• 1 ≤ A_i + B_i - 1 ≤ M
• 1 ≤ M ≤ 10⁹

各テストケースに対し、

Case #X: P

という内容を1行出力してください。ここで X は 1 から始まるテストケース番号、P はシャッフル後のカードの山の上から W 番目にあるカードを表します。

예제 입력

3
1 1 1
1 1
2 3 1
2 1
2 1
2 1
5 3 2
4 2
5 1
4 2

예제 출력

Case #1: 1
Case #2: 2
Case #3: 2