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

問題

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

入力

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

N
K1 P1
K2 P2
.
.
.
KN PN

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

出力

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

入出力例

入力例1

3
10 3
2 10
4 2

出力例1

1
2
2