Problem Description

Given a positive number $n$, Kris needs to find a positive number $k$ and an array $\{a_i\}(a_i\in\{-1,1\})$ of length $k(1\le k\le n + 2)$, such that:

$$
\sum\limits_{i=1}^k a_i\times i^2 = 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 \leq T \leq 100)$ indicating the number of test cases.

Each of the next $T$ lines contains one integer $n(1 \leq n \leq 10 ^ 6)$.

It's guaranteed that $\sum{n} \leq 3 * 10 ^ 7$.

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 $i$th position denoting $a_i=-1$ and 1 denoting $a_i=1$.

If there are multiple answers, print any.

2
1
5

1
1
2
11