next up previous
Next: Master of my domain Up: Inaugural UTICPC Previous: Inaugural UTICPC

Casting out threes

Before pocket calculators were popular, students were taught a number of arithmetical tricks. One of these is the method of casting out threes to check for divisibility by 3. (It also works for nines.)

The method is as follows. To test the divisibility by 3 of a number n, write it out in decimal. Now add the digits to get n'. Then n is divisible by 3 if and only if n' is divisible by 3. (Incidentally, one can prove this by strong induction on n.) The only trouble is that it may not be obvious whether n' is itself divisible by 3. In that case, repeat the algorithm substituting n' for n.

Here's a worked out example:

Since 4 is not divisible by 3, we deduce that 346 is not divisible by 3.

Input: The input to your program is a positive integer d, followed by d data sets. Each data set consists of a positive integer n, with .

Output: The output for each n should be the string yes if n is divisible by 3, and no otherwise. There should be no spaces in the output: each number should be followed by a single newline character.

Sample input:


Corresponding sample output:


David Neto
Thu Jan 9 19:12:26 EST 1997