TWINGIFT2

It's Andreas' and Vaso's birthdays again*, and this time it's their grandfather's turn to get them gifts. The grandfather knows that Vaso plays chess and loves the chessboard he has in his living room, with its marble pieces. He decides she would be very happy if he gave her this as a gift. Additionally, both children admire their grandfather's coin collection, which gives him the idea for Andreas' gift: he will give him some of his coins. The only difficulty remaining for the grandfather is how to ensure that the gifts for both children are of equal value...

The grandfather calculates that the chessboard is worth ~B~ euros. His coin collection includes coins whose values are powers of ~3~, but there is only one coin of each type - that is, he has one coin worth ~1~ euro, one worth ~3~ euros, one worth ~9~ euros, one worth ~27~ euros, etc. Fortunately, his collection is very large (and the grandfather very wealthy) - you can assume that there are infinitely many coins in his collection, one for each power of ~3~.

Trying to find which coins he should give to Andreas so that their values sum to ~B~ euros, the grandfather sees that this is not always possible (that is, for all values of ~B~). He considers that he may complement Vaso's gift with some coins, so that the total value of both children's gifts is equal, and as he is good at mathematics, he proves that this is always possible.

Help the grandfather find which coins he should give to Andreas and which to Vaso (along with the chessboard), so that the total value of both children's gifts is equal.

Input:

The first line of the input will contain a positive integer ~T~: the number of queries your program must answer. Each of the next ~T~ lines will correspond to a query and will contain a positive integer ~B~: the value of the chessboard.

Output:

The output must contain ~T~ lines, each one corresponding to the answer to the respective query from the input. Each line should first contain the values of the coins that Vaso will take, in ascending order, followed by the character '#', and then the values of the coins that Andreas will take, also in ascending order. All values should be separated in pairs by a single space. If there are multiple correct answers for any query, you can output any of them.

Constraints:

• ~1 \le T \le 10~
• ~1 \le B \le 10^{18}~
• Time Limit: ~1~ sec.
• Memory Limit: ~64~ MB.
• For test cases with a total value of ~40%~, it will be ~1 \le B \le 10^6~.

Example of Input - Output:

input:

3
42
30
17

output:

3 9 27 # 81
# 3 27
1 9 # 27

Explanation of the example:

In the first question, Vaso will take the chessboard (~42~) and coins of value ~3~, ~9~, and ~27~, while Andreas will take a coin of ~81~ - ~42 + 3 + 9 + 27 = 81~. In the second question, Vaso will only take the chessboard - verifying that ~30 = 3 + 27~. In the third question, it holds that ~17 + 1 + 9 = 27~.

*The solution to this problem is not related to the solution of the twingift problem from phase B'- only the story has similarities.