← 返回题目列表

Codeforces · 2050/C

C. 无趣的数字

中文机器翻译题面 查看原题

给你一个数字$$$n$$$,长度不超过$$$10^5$$$。

您可以多次执行以下操作:选择其中一位数字,对其进行平方,然后用结果替换原始数字。结果必须是数字(即,如果选择数字 $$$x$$$,则 $$$x^2$$$ 的值必须小于 $$$10$$$)。

通过这些运算是否可以得到一个能被$$$9$$$整除的数字?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的唯一行包含数字$$$n$$$,没有前导零。数字长度不超过$$$10^5$$$。

保证所有测试用例的数字长度总和不超过$$$10^5$$$。

输出

对于每个测试用例,如果使用所描述的操作可以获得可被 $$$9$$$ 整除的数字,则输出“YES”,否则输出“NO”。

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

示例

输入 #1

9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632

输出 #1

NO
YES
YES
NO
NO
YES
NO
YES
YES

注意

在第一个示例中,从整数 $$$123$$$ 中,只能获得 $$$123$$$、$$$143$$$、$$$129$$$ 和 $$$149$$$,它们都不能被 $$$9$$$ 整除。

在第二个示例中,您需要将第二个数字替换为其平方;那么 $$$n$$$ 将等于 $$$342 = 38 \cdot 9$$$。

在第三个示例中,整数已经可以被 $$$9$$$ 整除。