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