Math Contest

Problem 2 of the 2016 International Mathematical Olympiad reads as follows.

Find every positive integer $n$ such that each cell of an $n \times n$ table can be filled with one of the letters I, M and O so that both of the following hold.

• In each row and each column, one third of the entries are I, one third are M and one third are O.
• If the number of cells on a diagonal is a multiple of three, then on that diagonal one third of the entries are I, one third are M and one third are O.

The rows and the columns of the table are numbered 1 to $n$ in order, so each cell corresponds to a pair of integers $(i, j)$ with $1 \le i, j \le n$. For $n > 1$ the table has $4n - 2$ diagonals of two types. A diagonal of the first type consists of all cells with the same value of $i + j$, and a diagonal of the second type consists of all cells with the same value of $i - j$.

The answer to that problem is every positive integer divisible by 9, that is, every $n$ that can be written as $n = 9k$ for a positive integer $k$. You are in a programming contest rather than the olympiad, so the question changes. Given a positive integer $x$, decide whether $x$ can be used as $n$ in the problem above.

The first line contains the number of test cases $T$ ($1 \le T \le 1000$).

Each of the next $T$ lines contains one integer $x$ ($1 \le x \le 10^{100000}$). Every $x$ is written in decimal with no leading zeros.

For each test case, print YES if $x$ can be used as $n$, and NO otherwise, one answer per line and without quotes.