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}\)
5 1 6 11 9 19
1 1 2 3 9 3 1 3 27 2 1 27 3 1 3 81
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor