Statement

你有一个n行m列的网格。我们称一组三个格子（无序）是有魔法的，当且仅当这三个格子被包含在同一个$2 \times 2$的区域内。

现在请你在网格上选出一个四连通块，使得选出的格子中恰好有$k$组有魔法的格子。

Task

input

本题有多组数据。

第一行一个整数$T$表示有$T$组数据。

接下来$T$行每行三个整数$n,m,k$，意义见题目描述。

output

对于每组数据，如果无解，输出-1。否则输出n行，每行一个长为m的字符串。

如果第i行第j列的格子被选择了那么第i行字符串的第j个字符输出'1'，否则输出'0'。

请确保两组数据之间输出一个额外的空行。

如果有多组解，输出任意一组均可。

Sample I

input

3
3 3 1
3 3 3
3 3 4

output

110
100
000

010
111
100

010
111
010

Constraints

$\textbf{subtask 1(10 pts)}$:$n \times m \leq 16$

$\textbf{subtask 2(10 pts)}$:$n=3$

$\textbf{subtask 3(10 pts)}$:$n \le 7,\sum m \le 100$。

$\textbf{subtask 4(10 pts)}$:$n \leq 7$，依赖subtask1,2,3。

$\textbf{subtask 5(10 pts)}$:$k \leq 4(n-2)(m-1),n \le m$

$\textbf{subtask 6(50 pts)}$:无特殊限制，依赖subtask4,5。

对于所有数据，$$3 \leq n,m \leq 100000,0 \leq k \leq 10^9,\sum n \times m \leq 5000000$$。