Description

有一个n*n的棋盘，每个格子上有一个非负的整数。目标是求出从最左上的格子到最右下的格子的可行路径总数。每次只能向右边或者下面跳。 格子上的整数代表着从这个格子起跳后，向下或向右跳过的格子数，向一个会跳出棋盘边缘的方向跳是被禁止的。 比如n=5，最左上的格子的坐标为（1，1），这个格子上的整数为2，那么若从这个格子向右跳，则会跳到（1，3），向下跳则会跳到（3，1）。

Input

输入包括不多于30组的测试数据，以整数-1结束输入。 每组数据第一行以棋盘的行数n开始，4 <= n <= 34，接下来n行，每行有一个n长的数字串，中间没有空格。

Output

输出从最左上格到最右下格的可行路径总数。结果小于2^63。

Sample

Input

4
2331
1213
1231
3110
4
3332
1213
1232
2120
5
11101
01111
11111
11101
11101
-1

Output

3
0
7