Интересная последовательность

Последовательность 011212201220200112... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.

0 → 01 → 0112 → 01121220 → ...

Требуется найти m-ю цифру последовательности.

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

Первая строка содержит количество тестов n (1 ≤ n ≤ 1000). Далее следуют n строк, каждая из которых содержит m (1 ≤ m ≤ 2^63 - 1) - номер искомой цифры последовательности.

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

Для каждого теста выведите в отдельной строке цифру, стоящую на m-ом месте в описанной последовательности.

Примеры