小明迷上了机器人，一天她带着机器人参加了走迷宫比赛。 迷宫由N*N个方格组成，每个方格均被组织者事先标上了“0”或“1”（左上角第一个方格和右下角最后一个方格一定是“0”）。如果相邻的方格是“0”时则可以进入，而如果是“1”时则表示此路不通。比赛的规则是： 从迷宫的左上角第一个方格的入口处进入，从右下角最后一个方格出来，每个选手有初始分n×n，每经过一个标有“0”的方格，选手的分自动减去1分，当走出迷宫后，选手的分最高者为优胜者。 现在小明要为机器人编一个程序，要为机器人拿到最高分。

每个文件的第一行是一个整数N（3≤N≤40），接下来有N行，每行均有N个由0 和1组成的数据

一个整数，走完迷宫以后的最高分。

4 
0011
1000
0001
1000

9