In ACM labs, there are only few members who have girlfriends. And these people can make FFF Party angry easily. One day, FFF Party prepared a function FF and a set SS.

 

\displaystyle F(x)=\left\{ \begin{aligned} 1,&& n = 1,2 \\ F(n - 1) + F(n - 2), && n\ge3 \end{aligned} \right.F(x)={1,F(n−1)+F(n−2),​​n=1,2n≥3​

 

There are several unequal positive integers f_ifi​ in the set SS.

They calculated the value of W = \sum_{f \in S} F(F(f))W=∑f∈S​F(F(f)) , and tried to cause WWdamage to those who have girlfriends. Suppose you are not a single dog and have been attacked. Now, give you the value of WW and please write a program to calculate these f_ifi​ in set SS.

Input

The first line consists of a single integer TTdenoting the number of test cases.

TT lines follow, with an integer in each, denoting the result of WW.

Output

For each test case, print a sequence of space-separated integers f_ifi​ satisfying the equation.

If there are more than one answers, please print the lexicographically smallest one.

If there’s no such sequence, print -1−1 instead.

Constraints

1 \le T \le 101≤T≤10

1 \le W \le 10^{100,000}1≤W≤10100,000

样例输入复制

2
1
3

样例输出复制

1
1 2 3

   队友说是暴力？。

import java.math.BigInteger;
import java.util.Scanner;
//import java.io.FileOutputStream; 
//import java.io.PrintStream;
//import java.io.FileNotFoundException;

public class Main {
	public static void main(String[] args) {// throws FileNotFoundException {
		// TODO 自动生成的方法存根
		
//		PrintStream ps = new PrintStream("D:\\Albert\\out.txt");
//		System.setOut(ps);
		
		BigInteger ONE = BigInteger.ONE;
		BigInteger ZER = BigInteger.ZERO;
		BigInteger TWO = BigInteger.valueOf(2);
		BigInteger THR = BigInteger.valueOf(3);
		BigInteger FOR = BigInteger.valueOf(4);
		BigInteger FIV = BigInteger.valueOf(5);
		BigInteger SIX = BigInteger.valueOf(6);
		BigInteger SEV = BigInteger.valueOf(7);
		BigInteger EIG = BigInteger.valueOf(8);
		BigInteger NIN = BigInteger.valueOf(9);
		BigInteger TEN = BigInteger.valueOf(10);
		BigInteger res[] = new BigInteger[30];
		Scanner sc = new Scanner(System.in);
		for(int i = 1; i <= 29; ++i)
		{
			BigInteger n = BigInteger.valueOf(i);
				n = n.subtract(BigInteger.ONE);//
				BigInteger a[][] = { { ONE, ONE }, { ONE, ZER } };
				BigInteger b[][] = { { ONE, ZER }, { ZER, ONE } };// 单位矩阵
				while (n.compareTo(ZER) != 0) {
					if ((n.and(ONE)).compareTo(ONE) == 0) {
						b = q(a, b);
					}
					a = q(a, a);
					n = n .divide(TWO);
				}
				n = b[0][0];
				n = n.subtract(ONE);
				
//				System.out.print(i);
//				System.out.print(' ');
//				
//				System.out.print(n);
//				System.out.print(' ');
				
				a[0][0] = b[0][0] = ONE;
				a[0][1] = ONE;
				a[1][0] = b[1][1] = ONE;
				a[1][1] = b[0][1] = b[1][0] = ZER;
				
				while (n.compareTo(ZER) != 0) {
					if ((n.and(ONE)).compareTo(ONE) == 0) {
						b = q(a, b);
					}
					a = q(a, a);
					n = n .divide(TWO);
				}
				res[i]= b[0][0];
				
//				System.out.println(res[i]);
		}
		
//		for(int i = 1; i <= 10; ++i)
//			System.out.println(res[i]);
		
		int t = sc.nextInt(), idx;
		int ans[] = new int[30];
		BigInteger tar;
		while((t--) > 0)
		{
			idx = 0;
			tar = sc.nextBigInteger();
//			System.out.println(tar);
			for(int i = 29; i >= 1; --i)
			{
				if(tar.compareTo(TEN) < 0)
				{
					
				if(tar.compareTo(NIN) == 0)
				{
					ans[idx++] = 5;
					ans[idx++] = 4;
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(EIG) == 0)
				{
					ans[idx++] = 5;
					ans[idx++] = 3;
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(SEV) == 0)
				{
					ans[idx++] = 5;
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(SIX) == 0)
				{
					ans[idx++] = 5;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(FIV) == 0)
				{
					ans[idx++] = 4;
					ans[idx++] = 3;
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(FOR) == 0)
				{
					ans[idx++] = 4;
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(FOR) == 0)
				{
					ans[idx++] = 3;
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(THR) == 0)
				{
					ans[idx++] = 3;
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(TWO) == 0)
				{
					ans[idx++] = 2;
					ans[idx++] = 1;
				}
				else if(tar.compareTo(ONE) == 0)
				{
					ans[idx++] = 1;
				}
				tar = ZER;
			}
				if(tar.compareTo(res[i]) >= 0)
				{
					tar = tar.subtract(res[i]);
					ans[idx++] = i;
				}
			}			
			if(tar.compareTo(ZER) == 0)
			{
				for(int i = idx - 1; i > 0; --i)
				{
					System.out.print(ans[i]);
					System.out.print(' ');
				}
				System.out.println(ans[0]);
			}
			else
				System.out.println(-1);
		}
		
	}

	static BigInteger[][] q(BigInteger a[][], BigInteger b[][]) {//
		BigInteger value1 = (a[0][0].multiply(b[0][0])).add((a[0][1].multiply(b[1][0])));// 左上
		BigInteger value2 = (a[0][0].multiply(b[0][1])).add((a[0][1].multiply(b[1][1])));// 左上
		BigInteger value3 = (a[1][0].multiply(b[0][0])).add((a[1][1].multiply(b[1][0])));// 左上
		BigInteger value4 = (a[1][0].multiply(b[0][1])).add((a[1][1].multiply(b[1][1])));// 左上
		BigInteger c[][] = new BigInteger[2][2];
		c[0][0] = value1;
		c[0][1] = value2;
		c[1][0] = value3;
		c[1][1] = value4;
		return c;
	}
}