2050C.md (1746B)
1 Source: https://codeforces.com/problemset/problem/2050/C 2 3 C. Uninteresting Number 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a number $n$ with a length of no more than $10^5$. 22 23 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$). 24 25 Is it possible to obtain a number that is divisible by $9$ through these operations? 26 27 Input 28 29 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The only line of each test case contains the number $n$, without leading zeros. The length of the number does not exceed $10^5$. 32 33 It is guaranteed that the sum of the lengths of the numbers across all test cases does not exceed $10^5$. 34 35 Output 36 37 For each test case, output "YES" if it is possible to obtain a number divisible by $9$ using the described operations, and "NO" otherwise. 38 39 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. 40 41 Example 42 43 Input 44 45 ``` 46 9 47 48 123 49 50 322 51 52 333333333333 53 54 9997 55 56 5472778912773 57 58 1234567890 59 60 23 61 62 33 63 64 52254522632 65 ``` 66 67 Output 68 69 ``` 70 NO 71 YES 72 YES 73 NO 74 NO 75 YES 76 NO 77 YES 78 YES 79 ``` 80 81 Note 82 83 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$. 84 85 In the second example, you need to replace the second digit with its square; then $n$ will equal $342 = 38 \cdot 9$. 86 87 In the third example, the integer is already divisible by $9$.