#P0018. 九倍平方数

九倍平方数

题目描述

图片

芙宁娜给你一个长度不超过 10510^5 的数字 nn 。

旅行者可以多次进行下面的运算:选择其中一位数字,将其平方,然后用运算结果替换原来的数字。结果必须是一位数字(也就是说,如果您选择数字 xx ,那么 x2x^2 的值必须小于 1010 )。

芙宁娜的幸运数是所有 99 的倍数,她想知道,通过若干次这样的运算,有可能得到一个芙宁娜的幸运数吗?

输入格式

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

每个测试用例的唯一一行包含数字 nn ,不含前导零。数字长度不超过 10510^5 。

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

输出格式

对于每个测试用例,如果可以通过所述操作得到一个能被 99 整除的芙宁娜的幸运数,则输出 YES,否则输出 NO。

样例 #1

样例输入 #1

9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632

样例输出 #1

NO
YES
YES
NO
NO
YES
NO
YES
YES

样例解释

在第一组样例中,从整数 123123 中只能得到 123123 、 143143 、 129129 和 149149 ,它们都不能被 99 整除。

在第二组样例中,需要将第二个数字替换为它的平方,那么 nn 就等于 342=38⋅9342 = 38 \cdot 9 。

在第三组样例中,整数已经可以被 99 整除。