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}\)