Divisibility by 3

Given a large integer represented as a string, determine whether it is divisible by 3. A number is divisible by 3 if and only if the sum of its digits is divisible by 3. That is, for a number ( N = d_1d_2\dots d_n ), compute ( S = d_1 + d_2 + \dots + d_n ) and check if ( S \mod 3 = 0 ). This problem requires reading input from standard input (stdin) and writing the results to standard output (stdout), one result per test case.

inputFormat

The input begins with an integer ( T ) (( 1 \le T \le 1000 )) indicating the number of test cases. It is followed by ( T ) lines, each containing one non-negative integer represented as a string. The integer may be very large, so it is provided in string format.

outputFormat

For each test case, print a line containing either "YES" if the number is divisible by 3, or "NO" otherwise.## sample

3
123
111111
987654321

YES
YES
YES