题目内容

小塔在一个$4×4$的网格里玩贪吃蛇，从第二步开始每-次操作都要完整经过如下步骤：

• 选择一个方向，可以保持原来方向、顺时针旋转 $90$°或逆时针旋转 $90$°；

• 沿刚刚选定的方向，前进一个单位，需要保证操作在网格范围内且未走过，否则会发生碰撞并终止游戏；

如果在某一次操作中，小塔无路可走，游戏会立即中止。

现在小塔已经进行了几次操作，他想知道，如果继续这一局游戏，有没有可能走满全部 $16$ 个格子；如果不行，他至少需要进行几次“反悔”，即撤销当前存在的最后一步操作(指游戏操作，而不是反悔刚刚的“反悔”操作)。

输入描述

输入一个$4$行$4$列的数字矩阵，矩阵中数字为$0$则表示这个地方没被操作过，数字为 $x$ 表示第 $x$ 步走过这个格子，保证给出的矩阵中存在$1$，且是一个合法操作方案。

输出描述

在一行上输出一个整数，代表最少需要的反悔次数。

样例1

输入

1 2 0 0
4 3 0 0
5 6 7 8
0 0 0 0

输出

1

说明

撤回第八步之后可以得到的走满 $16$ 格方案为

1 2 9 10

4 3 8 11

5 6 7 12

16 15 14 13

样例2

输入

1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13

输出

0

说明

不需要反悔