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}\)
In the first test case, of the example n = 1 and if we write all the subsets in increasing order of the sum of their elements the set {1} comes at the 1st position.
In the second test case, the set {3,9} comes at the 6th position.
In the third test case, the set {1,3,27} comes at the 11th position.
