背景

最近在方块鸟的同学间兴起了「桌游」热，比如棋类的如飞行棋、五子棋、军棋、斗兽棋，卡牌类的如三国杀，模拟策略类的比如大富翁、卡坦岛等等。想要在这些游戏里面取得胜利，需要开动脑筋制定最优策略，但有时又得拥抱运气 （比如飞行棋里一直仍不出6 ），是很好的娱乐活动。

描述

这条，小H从家里带来了一副「蛇棋」，他说在家里和爸爸妈妈哥哥姐姐表弟表妹玩的不亦乐乎，就想到带来方块鸟和其他同学一起玩了。

小H说，他家里还有很多像这样的「蛇棋」棋盘，每个的大小（格子数量）、蛇和梯子的位置都不一样，今天就只带了这么一个过来给大家试试。

小方没有玩过「蛇棋」，小H就在给他介绍了一下游戏规则：

首先是每个人都拿一个棋子代表自己，从棋盘的1号格子出发。玩「蛇棋」需要用到一枚骰子，骰子有六个面，对应1～6的点数。所有人按顺序轮流投骰子，投到几走几步。

如果遇到梯子「梯底」可以往上爬到梯子的上面，一下子前进很多步；但是如果遇到蛇头，表示遭蛇吻，请回到蛇尾那格。胜负由谁先走到终点决定，注意如果在终点附近，掷出的骰子点数超过到达终点的步数，则必须往回走，只有点数与到达终点的步数吻合才算达成。

他们赶紧试了几盘，果然是紧张刺激的游戏呀！有时候明明已经领先很多，却不小心走到蛇头，倒回了很多格，而有时候，又能顺利踏上梯子逆风翻盘。而最惨的，眼睁睁的看着终点就在眼前，却怎么都投不出刚好到达终点的点数，被迫在终点跟前来来回回。

快乐的时光过的特别快，一天就这样结束了，他们一边走路回家一边讨论「蛇棋」游戏。小方和小块、小鸟说，你们说，如果运气足够好，每次都投出想要的点数，最少多少回合能走从起点走到终点呢？

小块和小鸟说，啊，这还不简单，我们懂编程啊，直接写个程序不就知道咯，下次来方块鸟，我们就把这程序写出来。可是他们觉得「蛇棋」太好玩了，下次到方块鸟的时候，根本就不想写，所以这个任务就交给你了。请你根据棋盘的信息，计算出到达终点需要的最少步数。

输入输出格式

输入

第一行为一个整数$N$，表示棋盘有$N$行$N$列。 ($1 ≤ N ≤ 100$)

随后$N$行，每行$N$个以空格分割的非负整数$x$，表示从1开始每个格子的信息。其中， ($0 ≤ x ≤ N$)

• $x$为0，则表示这是一个普通的格子，
• $x$不为0，则表示该格子是蛇头或梯底，连到$x$号格子。

输出

一个整数，表示从起点到终点最少的要几次骰子。

样例

5
0 0 11 0 0
17 0 0 18 12
0 0 0 4 0
0 0 0 8 0
0 20 0 16 0

3

样例1说明

这个棋盘如上图所示，最少的次数为3。

• 从1号格子出发，第一次投5，到达6号格子，爬梯子到达17号格子；
• 第二次投6，到达23号格子；
• 第三次投2，到达25号格子，到达终点；