Migrated from Lutece 1702 “Swap-Plus” puzzle

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有一种交换拼图的游戏是由4 x 4的网格组成的，里面包含了1 - 16这些数字，并且每个数字只出现一次。每个数字包含两个数位，意味着1 - 9这些数字有一个前导0。对于这个游戏的任意一种操作，有以下规则：
可以交换任意两个元素的位置；
可以交换任意两行的位置；
可以交换任意两列的位置；
现在你的任务是找到一种最小操作数使得原图变成以下模样：

Input

对于每组数据包括4行，每行有4个数字，按照题意给出1 - 16所在的初始位置（特别注意的是，1 - 9这些数字包含一个前导0）。

Output

对于每组数据，输出一个整数，代表将原图变成题意描述的图的最小操作数。

Samples

09 11 05 12
10 07 06 08
01 03 02 04
13 16 14 15

4

Note

Resources

2017 UESTC Training for Search Algorithm & String