006 - 残り物には髪生える?

時間制限 1 秒 / メモリ制限 64 MB / 得点 35 / x 23 /


TLE
1sec
MLE
64MB
得点
35

問題

この世界では他人の髪の最後の1本を抜くと抜いた人は髪がフサフサになるという伝説があった。そこでOHTおじさんは、既に禿げかけているおじさん(抜かれる人)をN人集め儀式をすることにした。この伝説には1人で髪を抜き続けてもフサフサにはならないというルールがあったので、OHTおじさんは仲間のIDAおじさん達(抜く人)も儀式ごとにP人呼ぶことにした。儀式の内容は、K本の髪からP人が順番に1本ずつ髪を抜く。P人目が髪を抜いた時点でまだ髪が残っていれば、また1人目から順番に髪を抜くという手順だ。OHTおじさんは不正をするために、KとPが与えられたとき、何人目が最後に髪を抜くかを知るプログラムの作成をあなたに頼んだ。

入力

入力は以下の形式で与えられる。

N
K1 P1
K2 P2
.
.
.
KN PN

1行目には儀式を行う回数N(1≤N≤100)が与えられる。 続くN行に、i回目の儀式におけるおじさんの髪の本数Ki(2≤Ki≤1000)と、 儀式に参加する人数Pi(2≤Pi≤1000)が与えられる。

出力

それぞれの儀式について、何人目が最後の髪を抜くかを出力する。

入出力例

入力例1

3
10 3
2 10
4 2

出力例1

1
2
2