Last week Andrea explained to her little students the divisibility rule for 3. “A number is divisible by 3 — she told them — if the sum of the digits is divisible by 3”. In order for them to practise it, she decided to give them homework. But she was in a hurry and, instead of giving them many different numbers, she decided to give them just a few. Each exercise was composed of a number n that should be used to build a big number concatenating all the numbers between 1 and n. For example, for n = 2, the number would be 12, when n = 6 would be 123,456, and for n = 13 it would be the long 12,345,678,910,111,213. Andrea asked them whether those cre- ated numbers were or not divisible by 3. This trick let her give them exercises with a small formulation but with a long solution. Now it is time to check the students responses, and the idea has backfired on her. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following. Each test case contains the number 1 ≤ n ≤ 109. Output For each test case, print ‘YES’ if the created number is multiple of 3, and ‘NO’ otherwise. Sample Input 3 2 6 130000000 Sample Output YES YES NO