Diamond Cipher

A renowned jewelry company has hired you to build safe-securing software. The company makes two kinds of safes for storing diamonds: one with $20$ switches and one with $200$ switches. To open a safe you need a password made of digits. Write a program that, given a password, tells you how to set the switches.

The switches are numbered starting from $0$, and switch $i$ is assigned the value $3^i$. Each switch has three states: Up, Middle, and Down. The safe opens when the sum of the values of the switches turned Up, minus the sum of the values of the switches turned Down, equals the password.

Write a program that:

• reads the safe passwords from standard input,
• computes a switch setting for each password,
• writes the result to standard output.

The first line contains the number of passwords $N$ ($1 \le N \le 250$). Each of the next $N$ lines contains one safe password, given as a non-negative integer with no leading zeros. In half of the tests every password corresponds to a safe with $20$ switches; in the other half a safe with $200$ switches may be required.

For each password, print the switch setting that opens the safe on two lines. On the first line, print the number of switches turned Up, followed by their numbers in ascending order. On the second line, print the number of switches turned Down, followed by their numbers in ascending order. Separate all numbers on a line with a single space. If no switch is turned Up (or Down), print just $0$ on that line.