You are given a set \(S\) consisting of non-negative powers of three \(S=\{1,\ 3,\ 9,\ 27,\ ...\}\). Consider the sequence of all non-empty subsets of \(S\) ordered by the value of the sum of their elements. You are also given a single element \(n\). You are required to find the subset at the \(n^{th}\) position in the sequence and print it in increasing order of its elements.

Input format

The first line contains one integer \(q\) denoting the number of queries. \(t\) test cases follow.
The first line of each test case consists of a single integer \(n\).

Output format

In the first line, print the size of the \(n^{th}\) subset.
In the next line, print the elements of the \(n^{th}\) subset in increasing order separated by space.

Constraints

\(1\le t\le 10^5\\ 1\le n\le 10^{12}\)