Економічна гра "П&Т"

Задані два невід’ємних цілих числа A та B. Два гравці – Постачальник (П) і Транзитер (Т), ходячи по черзі і дотримуючись найкращої стратегії, грають у гру, в якій П завжди починає першим. За один хід потрібно від більшого з чисел відняти натуральне число, кратне меншому, щоб отримати невід’ємний результат. Програв той, хто не може зробити хід.

Вхідні дані

Перший рядок – кількість тестів 1 ≤ N ≤ 10. У наступних N рядках по два числа в кожному – значення A та B (A, B < 2·10^9).

Вихідні дані

У єдиному рядку послідовність з N чисел 1 або 2, записаних підряд без пропусків, де 1, 2 - номери гравців, що виграли (1 – виграв П, 2 – Т).

Приклади