Codeforces Global Round 26 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

implementation

math

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Large Addition

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA digit is large if it is between $$$5$$$ and $$$9$$$, inclusive. A positive integer is large if all of its digits are large.

You are given an integer $$$x$$$. Can it be the sum of two large positive integers with the same number of digits?

Input

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

The only line of each test case contains a single integer $$$x$$$ ($$$10 \leq x \leq 10^{18}$$$).

Output

For each test case, output $$$\texttt{YES}$$$ if $$$x$$$ satisfies the condition, and $$$\texttt{NO}$$$ otherwise.

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

Example

Input

11133720013939381434987654321234567891111111111111111142019841069119

Output

YES NO YES YES NO YES NO YES YES NO NO

Note

In the first test case, we can have $$$658 + 679 = 1337$$$.

In the second test case, it can be shown that no numbers of equal length and only consisting of large digits can add to $$$200$$$.

In the third test case, we can have $$$696\,969 + 696\,969 = 1\,393\,938$$$.

In the fourth test case, we can have $$$777 + 657 = 1434$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 22:17:26 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|