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?
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})$.
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.