311211: CF1950D. Product of Binary Decimals

D. Product of Binary Decimalstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Let's call a number a binary decimal if it is a positive integer and all digits in its decimal notation are either $0$ or $1$. For example, $1\,010\,111$ is a binary decimal, while $10\,201$ and $787\,788$ are not.

Given a number $n$, you are asked whether or not it is possible to represent $n$ as a product of some (not necessarily distinct) binary decimals.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases.

The only line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).

Output

For each test case, output "YES" (without quotes) if $n$ can be represented as a product of binary decimals, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes", and "Yes" will be recognized as a positive response).

ExampleInput

11
121
1
14641
12221
10110
100000
99
112
2024
12421
1001

Output

YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES

Note

The first five test cases can be represented as a product of binary decimals as follows:

• $121 = 11 \times 11$.
• $1 = 1$ is already a binary decimal.
• $14\,641 = 11 \times 11 \times 11 \times 11$.
• $12\,221 = 11 \times 11 \times 101$.
• $10\,110 = 10\,110$ is already a binary decimal.

题目大意：
这个问题是关于“二进制小数”的乘积。所谓的二进制小数是指一个正整数，其十进制表示中的所有数字都是0或1。例如，1010111是一个二进制小数，而10201和787788则不是。

给定一个数n，需要判断是否可以将n表示为一些（不一定是不同的）二进制小数的乘积。

输入数据格式：
第一行包含一个整数t（1≤t≤5×10^4）——测试用例的数量。
每个测试用例只有一行，包含一个整数n（1≤n≤10^5）。

输出数据格式：
对于每个测试用例，如果n可以被表示为二进制小数的乘积，则输出“YES”（不带引号），否则输出“NO”（不带引号）。
“YES”和“NO”的输出可以为任意大小写组合（例如，“yES”、“yes”和“Yes”都将被视为肯定回答）。题目大意： 这个问题是关于“二进制小数”的乘积。所谓的二进制小数是指一个正整数，其十进制表示中的所有数字都是0或1。例如，1010111是一个二进制小数，而10201和787788则不是。 给定一个数n，需要判断是否可以将n表示为一些（不一定是不同的）二进制小数的乘积。 输入数据格式： 第一行包含一个整数t（1≤t≤5×10^4）——测试用例的数量。 每个测试用例只有一行，包含一个整数n（1≤n≤10^5）。 输出数据格式： 对于每个测试用例，如果n可以被表示为二进制小数的乘积，则输出“YES”（不带引号），否则输出“NO”（不带引号）。 “YES”和“NO”的输出可以为任意大小写组合（例如，“yES”、“yes”和“Yes”都将被视为肯定回答）。