题目描述

司马懿喜欢玩一个 4x4 的数独游戏。规则如下：

• 每行包含数字 1 到 4，且不重复。
• 每列包含数字 1 到 4，且不重复。
• 棋盘被分为 4 个 2x2 的小块，每个小块包含数字 1 到 4，且不重复。

现在给定一个部分填充的 4x4 棋盘，其中 '*' 表示空白。保证只有一种恢复方式。请恢复棋盘。

输入格式

第一行一个整数 T (1 ≤ T ≤ 100)，表示测试用例的数量。 接下来有 T 个测试用例。每个测试用例前有一个空行，然后 4 行，每行 4 个字符。字符为 '1','2','3','4' 或 '*'。

输出格式

对于每个测试用例，输出一行 "Case #x:"，其中 x 是从 1 开始的编号。接下来 4 行，每行 4 个字符，表示恢复后的棋盘。

样例输入

3

****
2341
4123
3214

*243
*312
*421
*134

*41*
**3*
2*41
4*2*
  

样例输出

Case #1:
1432
2341
4123
3214
Case #2:
1243
4312
3421
2134
Case #3:
3412
1234
2341
4123

数据范围

1 ≤ T ≤ 100 保证每个测试用例有唯一解。