Задано два неотрицательных целых числа A и B. Два игрока – Поставщик (П) и Транзитер (Т), ходят по очереди и придерживаясь наилучшей стратегии, играют в игру, в которой П всегда начинает первым. За один ход нужно от большего с чисел вычесть натуральное число, кратное меньшому, получив при этом неотрицательный результат. Проиграл тот, кто не смог сделать ход.
Первая строка – количество тестов 1 ≤ N ≤ 10. В последующих N строк по два числа в каждой – значения A и B (A, B < 2·10^9).
В единственной строке последовательность из N чисел 1 или 2, записанных подряд без пробелов, где 1, 2 - номера выигравших игроков (1 – выиграл П, 2 – Т).