codeforces#P1950D. Product of Binary Decimals
Product of Binary Decimals
Description
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.
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$).
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).
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).
11
121
1
14641
12221
10110
100000
99
112
2024
12421
1001
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.