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