Mr.Avantgarde loves to ride his bicycle and visit all his CSI-DTU friends once in a while. His town is a N×N grid. He has to visit M friends marked by the letter 'F'. Empty land is marked with '.'. He is initially located at his house marked by 'S' and after visiting all of his friends he will return to his home. He is allowed to move horizontally, vertically and diagonally to adjacent squares only. Additionally, each cell in a grid has some altitude and the tiredness associated with the whole trip is equal to the difference between highest altitude and the lowest altitude encountered in the whole trip. But Mr.Avantgarde is very lazy and wants you to calculate the minimum tiredness he can achieve in the whole trip.

Input

The first line of input contains an integer N (2 <= N <= 50). The following N lines represents the required grid.The character ‘S’ will appear exactly once, while the character ‘F’ will appear at least once. The following N lines each contain N positive integers less than 10^6, the altitudes of the fields mentioned in the corresponding above grid.

Output

Print the least possible tiredness that Mr.Avantgarde can achieve.

Sample

Input
3
S..
.FF
...
3 2 4
7 4 2
2 3 1

Output
2