24553번 - 팰린드롬 게임

상윤이와 승우는 통산전적 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을 출력한다.