说明

xgg想完成他的人生目标但总有ljwsm阻碍他，给出一个nn的地图，1代表xgg可以立足的地方，0代表wsm所在地方，xgg不能立足。xgg不能一步登天要从起点到终点。但是由于不能经过wsm所在地方，如果起点终点被wsm占领区域截断，则要挖地道。xgg精的一比，他想损耗最少的精力，（假设要从（x1，y1）挖到(x2,y2）,则小狗狗需要耗费(2的(x1-y1)(x1-y1)+(x2-y2)*(x2-y2)次方个精力，但小狗狗的精力损耗值如果达到1e9+7则会归零，所以不一定距离越大xgg消耗精力越多)。指定起点终点，求小狗狗从垃圾到人生目标区最少要花费的精力。（起点代表垃圾，终点代表人生目标，0代表ljwsm所在区域小狗狗不会去，小狗狗在1区行走不费精力，只有挖地道费精力）

输入格式

输入一个n代表地图大小输入一个n*n矩阵n<=50

输出格式

输出小狗狗到达人生目标最少消耗精力

样例

00001
11111
00111
00110
00110

1024

样例

01111
11111
11110
11010
11000

8192