The Last One is the Best

Time Limit : 1 sec, Memory Limit : 65536 KB

残り物には福がある

K 個の石から、P 人が順番に1つずつ石を取るゲームがあります。P 人目が石を取った時点で、まだ石が残っていれば、また1人目から順番に1つずつ石を取っていきます。このゲームでは、最後の石を取った人が勝ちとなります。KP が与えられたとき、何人目が勝つか判定するプログラムを作成してください。

入力

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

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
2
2

Source: PC Koshien 2014, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-9-13
http://web-ext.u-aizu.ac.jp/pc-concours/