팰린드롬 게임

상윤이와 승우는 통산 전적 1000전 500승 500패인 영혼의 라이벌이다.

누가 더 게임을 잘하는지 가리기 위해 마지막으로 한 판을 두기로 했다.

게임의 규칙은 다음과 같다.

1. $N$개의 돌이 쌓여 있는 돌 무더기에서 게임을 진행한다.
2. 상윤이가 먼저 시작하고, 그다음에는 승우, 상윤이 순서로 번갈아 가며 차례를 가진다.
3. 자신의 차례가 오면 돌 무더기에서 돌을 $x$개 가져올 수 있다. 이때 $x$는 팰린드롬 수여야 한다.
4. 자신의 차례에 가져올 돌이 없으면 그 사람이 패배한다.

팰린드롬 수란 $3$, $11$, $929$처럼 뒤집어도 같은 수가 나오는 양의 정수를 말한다. $010$처럼 앞에 의미 없는 $0$이 붙은 경우는 포함하지 않는다.

상윤이와 승우는 1000판을 치러 본 고수라서 항상 최선의 수만 둔다.

돌의 개수 $N$이 주어졌을 때 누가 이기는지 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1\,000$)

둘째 줄부터 $T$개의 줄에 걸쳐 돌 무더기에 쌓여 있는 돌의 개수 $N$이 주어진다. ($1 \le N \le 10^{18}$)

각 게임에서 상윤이가 이기면 0, 승우가 이기면 1을 출력한다.