C. Неинтересное число
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано число $$$n$$$ длины не больше $$$10^5$$$.

Вы можете любое количество раз сделать с ним следующее: выбрать одну из его цифр, возвести её в квадрат и заменить получившейся исходную цифру. При этом результат должен быть цифрой (то есть, если вы выбрали цифру $$$x$$$, то значение $$$x^2$$$ должно быть меньше $$$10$$$).

Можно ли такими действиями получить из исходного числа такое, которое будет делиться нацело на $$$9$$$?

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора содержит число $$$n$$$, без ведущих нулей. Длина числа не превосходит $$$10^5$$$.

Гарантируется, что сумма длин чисел по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если с помощью описанных операций можно получить число, делящееся на $$$9$$$, и «NO» иначе.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632
Выходные данные
NO
YES
YES
NO
NO
YES
NO
YES
YES
Примечание

В первом примере из числа $$$123$$$ возможно получить только $$$123$$$, $$$143$$$, $$$129$$$ и $$$149$$$, ни одно из них не делится на $$$9$$$.

Во втором примере нужно заменить вторую цифру на её квадрат, тогда $$$n$$$ станет равно $$$342 = 38 \cdot 9$$$.

В третьем примере число уже делится на $$$9$$$.