Light Up 是一款益智游戏。你的任务不是玩 Light Up，而是判断玩家给出的解法是否正确。

该游戏在一个正方形网格上进行。网格中包含一些障碍物，其中部分障碍物上标有 0 到 4 的数字。玩家必须在空地（open cells）上放置灯泡。每个灯泡可以照亮其上方、下方、左侧和右侧（不包括对角线）的所有空地，直到光线到达网格边缘或障碍物为止。玩家放置灯泡必须满足以下条件：

• 每一块空地都必须被照亮。
• 任意两个灯泡不能互相照射。
• 任何标有数字的障碍物，其上、下、左、右四个相邻位置的灯泡数量必须恰好等于该数字。对角线不计入。

以下是一个示例网格及其解法：

给定一个已放置灯泡的网格，判断它是否为一个合法的解。注意，如果网格中没有空地，且不违反任何其他约束，则该网格被视为平凡解。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 30$)，表示网格的行数和列数。

接下来的 $n$ 行，每行包含恰好 $n$ 个字符，字符集为 $\{'.', 'X', '?', '0', '1', '2', '3', '4'\}$。这就是网格，其中 '.' 表示空地，'X' 表示障碍物，'?' 表示灯泡，'0' 到 '4' 表示带有相邻灯泡数量约束的障碍物。

输出格式

输出一个整数，如果输入是一个合法的解，则输出 1，否则输出 0。

样例

样例输入 1

7
.?.0..?
..X.1?.
.X.?.2.
.....?.
?3?..2.
.?3.X?.
..?X?..

样例输出 1

1

样例输入 2

7
.?.0..?
..X.1?.
.X...2.
.....?.
?3?..2.
.?3.X?.
..?X?..

样例输出 2

0