给定整数 $N, M$ 和 $K$。其中 $N$ 和 $M$ 均大于等于 2。你需要在 $N$ 行 $M$ 列的网格中，将 $K$ 个格子涂成黑色，其余 $NM - K$ 个格子涂成白色。

在此，染色网格的“损失”（loss）定义如下： * 包含恰好 2 个黑色格子和 2 个白色格子的 $2 \times 2$ 子网格的数量。

请提供一种染色方案，使得损失最小化。 你需要处理 $T$ 组测试数据，并为每组测试数据提供一个解。

输入格式

输入通过标准输入给出，格式如下，其中 case$_i$ 表示第 $i$ 组测试数据：

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

每组测试数据的格式如下：

$N \ M \ K$

• 输入中的所有值均为整数。
• $1 \le T \le 10^5$
• $2 \le N, M \le 1500$
• $0 \le K \le NM$
• 对于每个输入文件，所有测试数据的 $NM$ 之和不超过 $4 \times 10^6$。

输出格式

按顺序输出每组测试数据的答案，以换行分隔。 对于每组测试数据，输出 $N$ 行，每行包含一个长度为 $M$ 的由 0 和 1 组成的字符串。 如果第 $i$ 行第 $j$ 个字符为 0，表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子被涂成白色；如果为 1，则表示该格子被涂成黑色。 如果存在多种使得损失最小的填充方式，输出其中任意一种即可。注意，不需要输出最小损失的值。

样例

输入 1

2
2 2 2
2 3 0

输出 1

10
01
000
000

说明

• 对于第一组测试数据，损失为 1，这是最小值。
• 对于第二组测试数据，损失为 0，这是最小值。