Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

WEIGHING - Weighing

You have a double-pan balance, some object and a collection of weights. Mass of the weight is always a power of 3 (so: 1, 3, 9, 27, 81...). For each integer k>=0 there is only one weight with mass 3k. The object was put on the left balance pan. Your task is to put some weights on the left and right balance pans in order to make it balanced.

Input

The first line of the standard input contains one integer t (t<101) which is number of test cases.

In each of the next t lines there is one number n (n<=109) which is the weight of the object.

Output

For each test output consists of three lines. In the first line print number of weights (number x) and then print x numbers which you have to put on the left balance pan in ascending order. The second line should involve information about the right balance pan in the same format. Third line is a blank one.

Example

Input:
2
50
156
Output:
3 1 3 27
1 81

2 9 81
2 3 243


Added by:Piotr Ką…kol
Date:2010-05-02
Time limit:2.197s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC SCM qobi VB.NET

hide comments
2012-04-17 23:18:32 Hallvard Norheim Bø
Looks like java is back on track now :)
2012-03-29 01:18:22 Piotr KÄ…kol
The right person has been informed.
; but for example ranking on polish SPOJ is off and won't be fixed in few weeks (sic!). So I wouldn't be optimistic.
2012-03-26 14:30:55 Hallvard Norheim Bø
Piotr: looks like spoj is broken after the upgrades. Can't get my java solution to even compile. On ideone.com it worked with "class Main{...", but even that won't work here :(
2011-08-26 12:09:07 HWK
@hallvabo: It's your turn. ;-)
2010-05-04 22:02:39 Piotr KÄ…kol
Corrected.
Thank You for Your remarks. :-)
2010-05-04 00:50:40 Jargon
You should clarify that
1) n = weight of object, and
2) the first line of output is what you must put on the left pan, and the second line of output is what you must put on the right pan.

Last edit: 2010-05-04 00:51:28
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.