수학 대회

2016년 국제 수학 올림피아드에 출제된 2번 문제는 다음과 같다.

$n \times n$ 표의 각 칸에 I, M, O 중 한 글자를 적어 아래 두 조건을 모두 만족시킬 수 있는 양의 정수 $n$을 모두 구하여라.

• 각 행과 각 열에서 I가 전체의 3분의 1, M이 3분의 1, O가 3분의 1이다.
• 어떤 대각선 위에 놓인 칸의 개수가 3의 배수이면, 그 대각선에서도 I가 3분의 1, M이 3분의 1, O가 3분의 1이다.

표의 행과 열에는 1부터 $n$까지 번호가 순서대로 붙어 있고, 각 칸은 $1 \le i, j \le n$인 정수 쌍 $(i, j)$에 대응한다. $n > 1$이면 표에는 두 종류의 대각선이 모두 $4n - 2$개 있다. 첫 번째 종류는 $i + j$가 같은 칸을 모두 모은 것이고, 두 번째 종류는 $i - j$가 같은 칸을 모두 모은 것이다.

이 문제의 답은 9의 배수인 양의 정수 전체다. 즉 어떤 양의 정수 $k$에 대하여 $n = 9k$로 쓸 수 있는 $n$이 답이다. 지금 참가한 대회는 올림피아드가 아니라 프로그래밍 대회이므로 질문을 바꾼다. 양의 정수 $x$가 주어질 때, $x$를 위 문제의 $n$으로 쓸 수 있는지 판정하라.

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

다음 $T$개의 줄에 각 테스트 케이스의 정수 $x$가 한 줄에 하나씩 주어진다. ($1 \le x \le 10^{100000}$) $x$는 앞에 0이 붙지 않은 십진수로 주어진다.

각 테스트 케이스마다 $x$를 $n$으로 쓸 수 있으면 YES를, 쓸 수 없으면 NO를 한 줄에 출력한다. 따옴표는 출력하지 않는다.