Test for Rikka

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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.

Sample Input

1 4

Sample Output

2 4 11 01

Hint

wange2014

Source

2015 Multi-University Training Contest 4

提交代码