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}$