Жадина

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

Вхідні дані

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

Вихідні дані

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

Приклади