L. Kyooma Loves Numbers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kyooma 喜欢可以被 $$$9$$$ 整除的数字，所以她想最大化这类数的数量。你将得到几个 $$$15$$$ 进制的数字。我们用 $$$A, B, C, D, E$$$ 来代表 $$$10, 11, 12, 13, 14$$$ 。

你可以执行以下操作$$$\textbf{零次或一次}$$$：选择给定数字的两个$$$\textbf{不同位}$$$，交换对应位置上的两个数字。

例如，我们有一个 $$$15$$$ 进制数 $$$C08$$$ ，可以生成的所有数字是： $$$C08, C80, 0C8, 80C$$$ 。

Input

每个测试点包含多组测试。

输入第一行包含一个正整数 $$$t$$$ $$$({1}\le{t}\le{20})$$$ — 测试的数量。

每个测试仅包含一行，行内包括一个$$$15$$$进制整数 $$$n$$$ $$$({0}\le{n}\le{15^{500^{2}}})$$$.

Output

对于每个测试，输出 "YES" 或 "NO" 代表对应 $$$15$$$ 进制数能不能在至多一次操作后变得能被 $$$9$$$ 整除。

Example
Input
6
9
DD
109
36
53
17
Output
YES
NO
YES
NO
NO
NO