Цікава послідовність#4894
Послідовність 011212201220200112... утворюється так: спочатку пишеться , потім повторюється наступна дія: уже написану частину дописують праворуч з заміною на , на , на , тобто
0 → 01 → 0112 → 01121220 → ...
Потрібно знайти -ту цифру послідовності.
Перший рядок містить кількість тестів (1 \leq n \leq 1000). Далі йде рядків, кожен з яких містить (1 \leq m \leq 2^{63} - 1) - номер шуканої цифри послідовності.
Для кожного тесту виведіть у окремому рядку цифру, яка стоїть на -му місці в описаній послідовності.
Приклад 1