Palindrome Game

Sangyoon and Seungwoo are fierce rivals with a record of 500 wins and 500 losses in 1000 games.

To settle who is better at games, they decide to play one final game.

The rules are as follows.

1. The game is played with a pile of $N$ stones.
2. Sangyoon moves first. After that, Seungwoo and Sangyoon alternate turns.
3. On your turn, you may take $x$ stones from the pile. Here $x$ must be a palindrome number.
4. If you have no stones to take on your turn, you lose.

A palindrome number is a positive integer that reads the same when reversed, such as $3$, $11$, and $929$. Numbers with leading zeros, such as $010$, do not count.

Both Sangyoon and Seungwoo have played 1000 games and always make the best move.

Given the number of stones $N$, print who wins.

The first line gives the number of test cases $T$. ($1 \le T \le 1\,000$)

Each of the next $T$ lines gives the number of stones $N$ in the pile. ($1 \le N \le 10^{18}$)

For each game, print 0 if Sangyoon wins and 1 if Seungwoo wins.