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.
输入解释
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$.
输出解释
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$.