Problem Description

As we know, Rikka is poor at math. At the test, Rikka finds that she cannot even do a single problem. There is one of the insane problems:

Given an integer $K$, she needs to come up with an $n \times n$ $01$ matrix $A$ and an integer $m$ which meet $B_{1,n}=K$, where $B=A^m$.

It is too difficult for Rikka. Can you help her?

Input

The first line of the input is a single integer $T\ (T=40)$, indicating the number of testcases.

Each of the next $T$ lines contains one integer $K\ (0 \leq K \leq 10^{18})$.

Output

For each testcase, the first line contains two space-separated integers $n,m\ (1 \leq n,m \leq 30)$.

In each of following $n$ lines print $n$ characters (0 or 1) - the matrix $A$ you find.

1
4

2 4
11
01

Author

XJZX