Bạn được cung cấp một số n có độ dài không quá 10⁵.

Bạn có thể thực hiện phép toán sau nhiều lần: chọn một trong các chữ số của nó, bình phương nó và thay thế chữ số ban đầu bằng kết quả. Kết quả phải là một chữ số (tức là, nếu bạn chọn chữ số x , thì giá trị của x² phải nhỏ hơn 10).

Có thể thu được một số chia hết cho 9 thông qua các phép toán này không?

Input :

     - Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 10⁴) — số lượng testcase 

     - t dòng tiếp theo mỗi dòng chứa 1 số n, không có số không đứng đầu. Độ dài của số không vượt quá 10⁵.

Đảm bảo rằng tổng độ dài của các số trong tất cả các trường hợp thử nghiệm không vượt quá 10⁵.

Output :

     - In ra "YES" nếu có thể thu được 1 số chia hết cho 9 và ngược lại in "NO"