Задано два неотрицательных целых числа \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{Т}).