Последовательность 011212201220200112200200120010... строится так:
сначала пишется 0, затем повторяется такое действие: уже написанную часть
приписывают справа с заменой 0 на 1, 1 на 2 и 2 на 0, т.е. 0 -> 01 -> 0112
-> 01121220 -> ...
Составить программу, которая для введенного пользователем N определяет N-й член последовательности.
В первой строке ввода находится количество тестов M. Далее следуют M строк,
каждая из которых содержит число N (1 <= N <= 2000000000).
Для каждого теста вывести N-й член последовательности в отдельной строке вывода.