• 수학적인 용어와 형식으로 표현한 문제 설명을 이해하는데 약간의 노력이 필요하지만, 문제를 이해하고 나면 풀이는 자명하다
• n이 2 이하일때에는, 1은 움직이지 않는다. 그러므로 1의 최종 위치는 변함없이 1이다
• n이 3이상인 경우에는 3-교환 시점에서 1이 인덱스 3으로 이동된다. 이렇게 3의 자리로 이동되고 나면 3은 2의 거듭제곱수가 아니기때문에 이후의 어떤 교환에서도 이동되지 않는다. 그러므로 1의 최종 위치는 3이다.

"""Solution code for "BOJ 31215. 이상한 섞기 연산".

- Problem link: https://www.acmicpc.net/problem/31215
- Solution link: http://www.teferi.net/ps/problems/boj/31215
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        n = sys.stdin.readline().rstrip()
        if n == '1' or n == '2':
            print('1')
        else:
            print('3')


if __name__ == '__main__':
    main()