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