K. An Easy Math Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baran wants to ensure that the problem Shaban prepared for the LCPC contest is approachable for the students. To make it more accessible, he has simplified the task as follows:

Given a very large number $$$n$$$ (where $$$0 \leq n \leq 10^{10^5}$$$), determine if $$$n$$$ is divisible by 9.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T (1 \le T \le 10^4)$$$. The description of the test cases follows.

The first and only line of each test case contains one integer $$$n$$$ $$$(0 \le n \le 10^{10^5})$$$ — the given large number.

It's guaranteed that the sum of the number of digits for all the test cases won't exceed $$$10^{5}$$$.

Output

Print Yes if the number is divisible by $$$9$$$; otherwise, print No.

Example
Input
10
333
234
18
09
666
8
11
116
568
71
Output
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No