Uninteresting Number
Contest: Codeforces Round 991 (Div. 3)
Difficulty rating: 1200
Tags: brute force, dp, math

You are given a number $$$n$$$ with a length of no more than $$$10^5$$$.

You can perform the following operation any number of times: choose one of its digits, square it, and replace the original digit with the result. The result must be a digit (that is, if you choose the digit $$$x$$$, then the value of $$$x^2$$$ must be less than $$$10$$$).

Is it possible to obtain a number that is divisible by $$$9$$$ through these operations?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains the number $$$n$$$, without leading zeros. The length of the number does not exceed $$$10^5$$$.

It is guaranteed that the sum of the lengths of the numbers across all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output "YES" if it is possible to obtain a number divisible by $$$9$$$ using the described operations, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, from the integer $$$123$$$, it is possible to obtain only $$$123$$$, $$$143$$$, $$$129$$$, and $$$149$$$, none of which are divisible by $$$9$$$.

In the second example, you need to replace the second digit with its square; then $$$n$$$ will equal $$$342 = 38 \cdot 9$$$.

In the third example, the integer is already divisible by $$$9$$$.

Example input:
9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632

Example output:
NO
YES
YES
NO
NO
YES
NO
YES
YES

Editorial:
The requirement that a digit must remain a digit imposes the following restrictions on transformations: we can transform $$$0$$$ into $$$0$$$, $$$1$$$ into $$$1$$$, $$$2$$$ into $$$4$$$, and $$$3$$$ into $$$9$$$. Any other digit squared will exceed 9, therefore, it cannot be transformed. Transformations involving $$$0$$$ and $$$1$$$ are useless, leaving us with two possible actions: squaring the digit $$$2$$$ or the digit $$$3$$$.
We will use the divisibility rule for $$$9$$$. It states that a number is divisible by $$$9$$$ if and only if the sum of its digits is divisible by $$$9$$$. Let's see how the sum of the digits will change with the possible transformations. If we square $$$2$$$, the sum of the digits increases by $$$2^2 - 2 = 2$$$, and if we square $$$3$$$, the sum of the digits increases by $$$3^2 - 3 = 6$$$.
We will count the number of digits $$$2$$$ in the number and the number of digits $$$3$$$ in the number. We can choose how many of the available digits $$$2$$$ and $$$3$$$ we will transform. Transforming more than 8 twos and more than 8 threes is pointless because remainders modulo $$$9$$$ their transformation adds to the sum will repeat.
Thus, the final solution looks like this: we calculate the sum of the digits in the number, count the number of digits $$$2$$$ and $$$3$$$. We will iterate over how many digits $$$2$$$ we change (possibly 0, but no more than 8), and how many digits $$$3$$$ we change (possibly 0, but also no more than 8). Let's say we changed $$$x$$$ digits $$$2$$$ and $$$y$$$ digits $$$3$$$, then the sum of the digits in the number increased by $$$x * 2 + y * 6$$$. If new sum is divisible by $$$9$$$, the answer is "YES". If such a situation was never reached during the iteration, then the answer is "NO".