逻辑城的公园总是由N×N个方格（2≤ N≤ 100），其中每个方块

具有前10个ASCII字母之一abcdefghijABCDEFGHIJ，小写或大写格式。

逻辑之城的人们在穿越公园时，自豪地只遵循一致的路径。例如

如果他们跳过小写的c，那么他们以后就不会允许自己跳过大写的c。

为了更准确地定义这一点，一致路径是一系列满足以下条件的方块：连续方块

正交相邻；小写和大写格式都没有字母。也就是说，

要么字母根本不在序列中，要么它只以小写形式出现，要么只以大写形式出现。

你必须写一个程序来帮助逻辑城的人们找到最短的长度

左上角坐标为（1,1）的正方形与正方形之间的一致路径

坐标（N，N），位于右下角。对于上面的示例公园，最短的一致

路径长度为13。

输入

输入包含几个测试用例。测试用例的第一行有一个整数N（2≤ N≤ 100）

公园的大小。接下来的N行每行包含N个字母的序列，用于定义公园。

输出

对于输入中的每个测试用例，程序必须输出一行，其中包含一个整数，长度为

最短的一致路径。如果没有一致的路径，则输出“-1”。

The parks in the City of Logic are always a grid of N × N squares (2 ≤ N ≤ 100), where each square has one of the first 10 ASCII letters, abcdefghijABCDEFGHIJ, in either lowercase or uppercase format. People from the City of Logic proudly follow only consistent paths when crossing parks. For example, if they step over a lowercase c, they will not allow themselves stepping over an uppercase C afterwards. To define this more precisely, a consistent path is a sequence of squares satisfying: consecutive squares are orthogonally adjacent; no letter occurs in both lowercase and uppercase format. That is to say, either a letter is not in the sequence at all, or it occurs only in lowercase, or only in uppercase format. DdaAaA D..... CBAcca C..... eEaeeE e..... bBbabB b.bab. DbDdDc DbD.D. fFaAaC ....aC You have to write a program to help the people from the City of Logic to find the length a shortest consistent path between the square with coordinates (1, 1), in the upper left corner, and the square with coordinates (N, N), in the lower right corner. For the example park above, the shortest consistent path has length 13. Input The input contains several test cases. The first line of a test case has a integer N (2 ≤ N ≤ 100), the size of the park. The next N lines contain, each one, a sequence of N letters, defining the park. Output For each test case in the input your program must output one line containing one integer, the length of a shortest consistent path. If there is no consistent path, output ‘-1’. Sample Input 6 DdaAaA CBAcca eEaeeE bBbabB DbDdDc fFaAaC 7 aAaaaaa aAaaaAa aAaaaAA aaAaAaa AaAaaAa aaAAaAa aaaaaAa Sample Output 13 -1