Problema número 397

¿Es múltiplo de 3?

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
15em

La semana pasada, Andrea explicó a sus pequeños alumnos la prueba de divisibilidad por 3. "Un número es divisible por 3 — les contó — si la suma de sus dígitos lo es".

Para que la practicaran, decidió ponerles ejercicios. Pero, en un dudoso alarde de astucia, en lugar de ponerles muchos números largos, por acortar, les planteó un enunciado extraño. Cada ejercicio era un valor n con el que formar un gran número a partir de la concatenación de todos los números entre 1 y n. Por ejemplo, para n = 2, el número generado era el 12, para n = 6 el 123.456, y para n = 13 el gigantesco 12.345.678.910.111.213. Lo que Andrea pedía a sus chicos era que le dijeran si el número construído así era o no divisible por 3.

Esto le permitió poner ejercicios de enunciado corto, pero de solución larga. El problema llega ahora, que toca corregirlos.

Entrada

La entrada comienza con el número de casos de prueba. Cada caso de prueba se muestra en una línea y es un número entero positivo menor que 109.

Salida

Para cada caso de prueba, el programa escribirá "SI" si el número formado es múltiplo de 3, y "NO" en caso contrario.

Entrada de ejemplo

3
2
6
130000000

Salida de ejemplo

SI
SI
NO