E. Simple Math
time limit per test
1 second
memory limit per test
1024 MB
input
standard input
output
standard output

As everyone knows, Cirno's favorite number is $$$9$$$!

Today, Cirno gets a positive integer $$$x$$$. She suddenly wonders: can she find another positive integer $$$k$$$ such that their product $$$x \cdot k$$$ becomes a number whose every digit is $$$9$$$ (for example, $$$9$$$, $$$99$$$, $$$999999$$$, and so on)?

Input

The input contains multiple test cases.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), denoting the number of test cases.

For each test case, the first line contains a positive integer $$$x$$$ $$$(1 \le x \le 10^{12})$$$.

It is guaranteed that the sum of all $$$x$$$ over a single test file does not exceed $$$10^{12}$$$.

Output

For each test case:

If there exists an integer $$$k$$$ satisfying the condition, output YES on a single line.

Otherwise, output NO on a single line.

You may print the answer in any letter case. For example, the strings yEs, yes, and Yes will all be accepted as affirmative answers.

Example
Input
4
3
10
7
12
Output
YES
NO
YES
NO
Note
  • In the first test case, $$$x = 3$$$. If we choose $$$k = 3$$$, then their product is $$$3 \times 3 = 9$$$, which satisfies the condition. Therefore, the answer is YES.
  • In the second test case, $$$x = 10$$$. It can be shown that there does not exist any positive integer $$$k$$$ such that $$$10 \cdot k$$$ consists entirely of the digit $$$9$$$. Therefore, the answer is NO.
  • In the third test case, $$$x = 7$$$. If we choose $$$k = 142857$$$, then their product is $$$7 \times 142857 = 999999$$$, which satisfies the condition. Therefore, the answer is YES.
  • In the fourth test case, $$$x = 12$$$. It can be shown that there does not exist any positive integer $$$k$$$ such that every digit of the product is $$$9$$$. Therefore, the answer is NO.