Shortening codes

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 3^k. 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<=10⁹) 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