Число называется троичным, если оно содержит только цифры $$$0$$$, $$$1$$$ и $$$2$$$. Например, следующие числа являются троичными: $$$1022$$$, $$$11$$$, $$$21$$$, $$$2002$$$.

Вам задано длинное троичное число $$$x$$$. Первая (самая левая) цифра числа $$$x$$$ гарантированно является $$$2$$$, остальные цифры числа $$$x$$$ могут быть $$$0$$$, $$$1$$$ или $$$2$$$.

Определим троичную операцию XOR $$$\odot$$$ над двумя троичными числами $$$a$$$ и $$$b$$$ (оба имеют длину $$$n$$$) как число $$$c = a \odot b$$$ длины $$$n$$$, где $$$c_i = (a_i + b_i) \% 3$$$ (где $$$\%$$$ — операция взятия по модулю). Другими словами, сложим соответствующие цифры и возьмем остатки от сумм при делении на $$$3$$$. Например, $$$10222 \odot 11021 = 21210$$$.

Ваша задача — найти такие троичные числа $$$a$$$ и $$$b$$$ (оба длины $$$n$$$ и без лидирующих нулей), что $$$a \odot b = x$$$ и $$$max(a, b)$$$ — минимально возможный.

Вам нужно ответить на $$$t$$$ независимых наборов входных данных.