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

Входные данные

Первая строка - количество тестов 1 ≤ N ≤ 10. В последующих N строк по два числа в каждой - значения A и B (A, B < 2·109).

Выходные данные

В единственной строке последовательность из N чисел 1 или 2, записанных подряд без пробелов, где 1, 2 - номера выигравших игроков (1 - выиграл П, 2 - Т).