Двое играют в игру "Жадина". Есть одна куча из n конфет, из которой двое по-очереди тянут любое количество конфет от 1 до k. Проигрывает тот, кто берёт последнюю конфету. Сколько конфет нужно взять первому игроку, чтобы победить при правильной игре обоих.
В первой строке записано количество партий t (1 ≤ t ≤ 10^5). В следующих t строках записано описание партий n (1 ≤ n ≤ 10^9) и k (1 ≤ k ≤ 10^9).
Для каждой партии выведите количество конфет, которое должен взять первый игрок, чтобы победить. Если первый игрок проигрывает выведите 0. Если ответов несколько, то выведите любой.