Ternarian Weights

In the Hellenic era there was a small island nation in the Mediterranean called Ternaria. It sat close to Sparta, but its mountains made it hard to conquer, so it stayed independent until the great earthquake of 729 BC sank it beneath the sea. Its civilization was advanced enough that some modern historians treat it as the original of the mythical city of Atlantis. The Greeks, and later the Romans, adopted much of what Ternaria worked out in science and mathematics. Ternarians were the first to standardize the pound, the unit we still use. Ternarian mathematics did every calculation in base 3. (Historians guess this honored King Ternary, who lost two fingers on each hand fighting the Spartans.)

Ternarian trade scales were the standard for centuries because they were accurate and easy to use. Ternarians were the first to build a scale with a pan on each side and a fulcrum in the middle. You put the object on the left pan, then add weights to both pans until the scale balances. That sounds strange today, since a modern scale takes weights on the right pan only. The modern method needs more weights, though. The Ternarian method needs just one weight for each power of three pounds: one weight of 1 pound, one weight of 3 pounds, one weight of 9 pounds, and so on.

Say you are weighing a 2 pound Ternarian hen. You put the hen on the left pan and the 3 pound weight on the right pan, which is too heavy, so you add the 1 pound weight to the left pan next to the hen and the scale balances. The sum of the weights on the right pan minus the sum of the weights on the left pan equals the weight of the object.

For a 21 pound Ternarian squash you put the 27 pound and 3 pound weights on the right pan and the 9 pound weight on the left pan next to the object, and the scale balances again.

Write a program that reads the weight of an object in base 10 and prints the weights to place in each pan.

The first line contains the number of test cases $n$. ($1 \le n \le 100$)

Each of the next $n$ lines contains the weight $x$ in pounds of the object placed on the left pan. ($0 \le x \le 10^9$)

Print two lines for each test case.

On the first line print left pan: followed by the weights for the left pan in descending order. On the second line print right pan: followed by the weights for the right pan in descending order. Separate weights with a single space and put a space before the first weight as well. If a pan takes no weights, print only its label on that line.

There is one weight for each power of three pounds, so exactly one arrangement balances the scale.

Print a blank line between consecutive test cases.