Problem Description

Given a positive number n, Kris needs to find a positive number k and an array {ai}(ai∈{−1,1}) of length k(1≤k≤n+2), such that:
 

∑i=1kai×i2=n

This is too hard for Kris so you have to help him.

 

Input

The input contains multiple test cases.

The first line contains an integer T(1≤T≤100) indicating the number of test cases.

Each of the next T lines contains one integer n(1≤n≤106).

It's guaranteed that ∑n≤3∗107.

 

Output

The output should contain 2T lines. For each test case, output two lines.

The first line contains one integer, k.

The second line contains a 01-string of length k representing the array, with 0 in the ith position denoting ai=−1 and 1 denoting ai=1.

If there are multiple answers, print any.

 

Sample Input

2 1 5

 

Sample Output

1 1 2 11

 题意：给定一个n，要求找到一个长度为k的数组，使得，其中只能为1或-1；

思路：经过分析可以发现"1001"为4、"1"为1、"0001"为2、"01"为3；于是对于任何n都可以通过01串构造出来；

AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;const int N=100010;int a[N];int main()
{int t;cin>>t;while(t--){int n;cin>>n;int m=n/4;switch (n%4) {case 0:cout<<n<<endl;break;case 1:cout<<n<<endl<<"1";break;case 2:cout<<n+2<<endl<<"0001";break;case 3:cout<<n-1<<endl<<"01";break;}for(int i=0;i<m;i++)cout<<"1001";puts("");}
}