Послідовність 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-ому місці в описаній послідовності.