Romer está cansado de perder en las apuestas, así que decide endeudarse con el Banco Difissil para jugarse un todo o nada en la Lotería Nacional. Su plan es comprar la mayor cantidad posible de boletos con el préstamo recibido. 

La noche antes de hacerlo, se le aparece un oráculo en sueños, de nombre Patuke, que le aconseja: Compra únicamente los boletos cuyos números sean divisibles por 3. 

Al despertar, Romer lo interpreta como una señal y decide seguir la recomendación. 

Sin embargo, de regreso a casa, Romer cae en un bache de su ciudad y todos sus boletos terminan dañados, con un dígito estropeado en cada uno. Incapaz de recordar los números originales, se le ocurre reconstruirlos reemplazando cada dígito perdido de la forma que resulte en el número más pequeño posible divisible entre 3. 

El problema es que Romer compró demasiados boletos, y no puede hacerlo manualmente. Por eso necesita tu ayuda para escribir un programa que lo resuelva.

Se te da un número \(1 \leq N \leq 2 \times 10^5\), el cual representa la cantidad de boletos que Romer compró, luego siguen \(N\) líneas, con un número de entre 10 a 100 dígitos, donde el número estropeado estará representado por un \(\ast\).

Por cada boleto muestra lo indicado, el número divisible por 3 más pequeño que pueda ser formado.