#描述#
一个N个节点的有向图,用一个N*N的邻接矩阵mat来描述.如果mat[i][j]=#则表示i到j没有边相连,如果mat[i][j]是一个大写字母X,则表示i到j有一条边,长度为X-‘A’+1(即AB..Z对应1,2,…,26),如果是小写字母x,则表示i到j有一条边,长度为x-‘a’+27(即ab..z对应27,28,…,52),注意,可能有从i到i的边的.
<BR>
<BR>
Elly想从第0个点走到第N-1个点.但是Elly有个条件,就是在她走过的路径上,没有哪一段的长度和是13的倍数.
<BR>
<BR>
例如,Elly从0->S1->S2->S3，走过的路程是T1，T2，T3,则根据她的条件,T1，T2,T3，T1+T2,T2+T3，T1+T2+T3这6个数都不能被13整除
<BR>
<BR>
现在让你求从Elly从0走到N-1点所需走的最短路程(一个点可以经过很多次).
<BR>

#格式#
##输入格式##
多组数据
每组数据第一行是一个整数N,表示有N个节点(N&lt=25)
然后是一个N*N的字符矩阵,意义如上所述.

##输出格式##
输出Elly从第0到N-1所需走的最短路程.如果不能到达输出-1。

#样例1#
##样例输入1##

4
#TQ#
h###
#j##
####

5
#AB##
###A#
###C#
####K
#####

##样例输出1##

-1
16

#限制#
1000ms
32768KB

#提示#

#来源#
zjut_DD