今天彼得明天还有额外的作业。老师给了他三个整数:n、m和k,并要求他在大小为n×m的方格上标记一个或多个方格。
标记的方块必须形成一个相连的图形,并且必须恰好有 k 个标记的方块三元组形成 L 形特罗米诺 - 所有三个方块都位于 2 × 2 的方块内。
如果允许从一个方格移动到公共边方格相邻的任何方格,则可以从任何方格到达任何其他方格,则这组方格形成一个连通图形。
彼得无法完成任务,所以他向你寻求帮助。帮助他创造这样的人物。
输入
输入数据包含一个或多个测试用例。第一行包含测试用例的数量 t (1 ≤ t ≤ 100)。
以下 t 个测试用例均由包含三个整数的行描述:n、m 和 k (3 ≤ n, m, n × m ≤ 105, 0 ≤ k ≤ 109)。
一个输入数据中所有测试的 n × m 值之和不超过 105。
输出
对于每个测试用例打印答案。
如果可以创建这样的图形,请打印 n 行,每行 m 个字符,使用星号“*”表示标记的正方形,并使用点“.”来表示未标记的。
如果没有解,则打印-1。
在测试用例之间打印空行。
示例
输入 #1
3 3 3 4 3 3 5 3 3 3
输出 #1
.*. *** .*. **. **. *.. .*. *** *..