Цікава послідовність

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

Приклади