题解 | 九倍平方数

import sys
from collections import Counter
T=int(input())
all_n=sys.stdin.read().splitlines()
res=list()
for i in range(T):
    n=all_n[i]
    n_s=str(n)
    n_list=list(map(int,n_s.strip()))
    c3=n_list.count(3)
    c2=n_list.count(2)
    #n的各位位数和
    sum_n=sum(n_list)
    #若各位位数和能整除9则n能整除9
    found=False
    if sum_n%9==0:
        res.append("YES")
        continue
    else:
        #只有2^2,3^2满足修改条件<10
        #2->2^2增量2
        #3->3^2增量6
        #只需满足sum_n+2*i(2的个数)+3*j(3的个数)能整除9即可
        for cnt2 in range(0,c2+1):
            for cnt3 in range(0,c3+1):
                if (sum_n+2*cnt2+6*cnt3)%9==0:
                    res.append("YES")
                    found=True
                    break
            #找到就退出
            if found:
                break
        if not found:
            res.append("NO")
print("\n".join(res))