Двоє грає в иру "Жадина". Є одна куча з n цукерок, з якої двоє по-черзі беруть будь-яку кількість цукерок від 1 до k. Проиграє той, хто бере останню цукерку. Скільки цукерок повинен взяти першому гравцю, щоб виграти при правильній грі обох.

Вхідні дані

В першому рядку записано кількість партій t (1 ≤ t ≤ 105). В наступних t рядках записано опис партій n (1 ≤ n ≤ 109) і k (1 ≤ k ≤ 109).

Вихідні дані

Для кожної партії виведіть кількість цукерок, яку повинен взяти перший гравець, щоб виграти. Якщо перший гравець програє виведіть 0. Якщо відповідей декілька, то виведіть будь-яку.