Jerry鼠为了躲避Tom猫的追打，逃进了一个迷宫，并且在迷宫内找到了一个格子睡觉。Tom一整天没有见到Jerry觉得无聊，于是决定去迷宫找Jerry，这个迷宫与寻常的迷宫有一些不一样：

a、这是是一个n*n大小的迷宫，迷宫每个小格子可能是墙、陷阱、路

b、为了简化这个问题，我们用#表示墙；用.表示路；用数字1--9表示陷阱

c、前面是墙的话，无法进入，当然Tom也无法走出迷宫范围（可以理解为迷宫四周都是墙，无法通行）

d、每个陷阱都有一个数字ki，表示Tom进入这个陷阱后需要ki*1000秒才能爬出这个陷阱，只有Tom爬出这个陷阱，才能继续走向下一个格子（1<=ki<=9）

e、Tom只能朝相邻的前后左右四个格子走，从当前所在的格子走向下一个格子固定花费100秒

现在Tom所在的格子为T，Jerry所在格子为J，请你帮Tom计算一下，他找到Jerry最少要花多少秒，如果永远都找不到Jerry，请输出Not Found。

第一行为一个正整数n（10<=n<=400），表示这是一个n*n的迷宫。接下来有n行，每一行n个字符，表示这个迷宫的布局。

输出一行，如果Tom能找到Jerry，则输出一个整数表示Tom找到Jerry所花的最少时间；如果Tom找不到Jerry，则输出Not Found。

数据范围：

40%数据：10<=n<=200

100%数据：10<=n<=400

广搜