На столі лежить n сірників. Грають двоє, ходять по черзі. За один хід гравець може взяти не більше m сірників, але не менше одного. Той, хто забере останній сірник виграє.

Хто виграє при вірній грі - перший чи другий гравець?

Вхідні дані

У першому рядку знаходиться кількість тестів t (1 ≤ t ≤ 100). Кожний з наступних t рядків містить кількість сірників n у кучці та максимальну дозволену кількість сірників m для взяття за один хід. Відомо що 1 ≤ n, m ≤ 2 * 109.

Вихідні дані

Вивести послідовність з t одиниць та двійок: 1 - якщо при правільній грі виграє перший і 2 - якщо виграє другий.