Задані два невід’ємних цілих числа \textbf{A} та \textbf{B}. Два гравці -- Постачальник (\textbf{П}) і Транзитер (\textbf{Т}), ходячи по черзі і дотримуючись найкращої стратегії, грають у гру, в якій \textbf{П} завжди починає першим. За один хід потрібно від більшого з чисел відняти натуральне число, кратне меншому, щоб отримати невід’ємний результат. Програв той, хто не може зробити хід. \InputFile Перший рядок -- кількість тестів \textbf{1} ≤ \textbf{N} ≤ \textbf{10}. У наступних \textbf{N} рядках по два числа в кожному -- значення \textbf{A} та \textbf{B} (\textbf{A}, \textbf{B} < \textbf{2·10^9}). \OutputFile У єдиному рядку послідовність з \textbf{N} чисел \textbf{1} або \textbf{2}, записаних підряд без пропусків, де \textbf{1}, \textbf{2} - номери гравців, що виграли (\textbf{1} -- виграв \textbf{П}, \textbf{2} -- \textbf{Т}).