该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

众所周知，琪露诺是幻想乡的一位数学天才baka。

琪露诺对⑨非常好奇，她日复一日地研究。最后她突发奇想的定义出⑨数。

她对⑨数的定义如下：

满足下列条件的其中之一即为⑨数:

1. 能被9整除的数
2. 数字中含有数字9
3. 可以写成 $x ^ 9$ 的形式，其中 $x$ 是正整数

例如：27，995，1（1的9次方）都是⑨数；而17,845都不是⑨数。

现在琪露诺给你 $n$ 个数，对于每个数 $a$ ，你需要判断 $a$ 是否为⑨数。

Input Format

第一行一个正整数 n ，表示琪露诺要给你的数的个数。
从第二行至第 n + 1 行，每行给出一个数 a 。

Output Format

输出 n 行。
对于每行给出的 a ，若 a 是⑨数输出'YES'，否则输出'NO'。

Sample

【样例1输入】

4
27
995
17
845

【样例1输出】

YES
YES
NO
NO

【样例2输入】

5
27
995
17
845
1

【样例2输出】

YES
YES
NO
NO
YES

Hint

对于 $30 \%$ 的数据，保证所有的⑨数只满足条件1。

对于 $75 \%$ 的数据，保证所有的⑨数满足条件1或条件2。

对于 $100 \%$ 的数据，保证所有的⑨数满足3个条件中的任意一个，$1 \leq a \leq 10 ^ 9$ ，$1 \leq n \leq 10 ^ 5$。

输入的所有数据全是整数。