#P0018. 九倍平方数
九倍平方数
题目描述

芙宁娜给你一个长度不超过 的数字 。
旅行者可以多次进行下面的运算:选择其中一位数字,将其平方,然后用运算结果替换原来的数字。结果必须是一位数字(也就是说,如果您选择数字 ,那么 的值必须小于 )。
芙宁娜的幸运数是所有 的倍数,她想知道,通过若干次这样的运算,有可能得到一个芙宁娜的幸运数吗?
输入格式
第一行包含一个整数 ( ) - 测试用例的数量。
每个测试用例的唯一一行包含数字 ,不含前导零。数字长度不超过 。
保证所有测试用例的数字长度之和不超过 。
输出格式
对于每个测试用例,如果可以通过所述操作得到一个能被 整除的芙宁娜的幸运数,则输出 YES,否则输出 NO。
样例 #1
样例输入 #1
9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632
样例输出 #1
NO
YES
YES
NO
NO
YES
NO
YES
YES
样例解释
在第一组样例中,从整数 中只能得到 、 、 和 ,它们都不能被 整除。
在第二组样例中,需要将第二个数字替换为它的平方,那么 就等于 。
在第三组样例中,整数已经可以被 整除。