Akshay has a lot of work to do this Bitotsav. So he asks god to create a copy of him for a day so that he can be present at 2 places at a time. God granted his wish.

The terrain of BIT is represented as a rectangular grid of squares, where each square either contains a building or is empty. Each empty square has an integer height between 0 and 9, inclusive. Today, Akshay has atleast some work to do at each building in the area. Akshay 1 and Akshay 2 both want to complete all the jobs in shortest total amount of time possible. The main problem in BIT is the huge campus. It only takes time to go from here to there. The time to do the job can be ignored.

From each square in the grid, you can only move to adjacent squares. Two squares are adjacent if they share an edge. You can only move between two empty squares if the absolute difference of their heights is less than or equal to 1. If the height difference is 0, it takes 1 minute to make the move, and if the absolute height difference is 1, it takes 3 mins.

You can always move to a building from any of its adjacent squares and vice versa, regardless of height. This is because the core members always find some way out to do things faster. Moving to or from a square containing a building takes 2 minutes. Moving from one building to another also takes 2 minutes. Akshays are allowed to enter buildings even if they are not at their final destinations.

After each job Akshay completes, he must return to his room to know about the details of his next task. Note that boys hostel is also a building.

Your task is to print the minimum time in mins in which the last job can be done and they return to their hostel. If it is not possible to do all the jobs, print -1 instead.

Input
One line containing an integer C, the number of test cases in the input.
For each of the C test cases:
The first line consists of M and N the size of the grid. M rows and N
columns.
The next M lines consists of a string which length is N. Each character
could be ‘$’, ‘X’ or digits from ‘0’ to ‘9’. '$' represents a building where
Akshay has some work to do , 'X' represents the boys hostel and the digits
'0'-'9' represent the heights of empty squares.

Output
For each test case, print the minimum time in minutes at which the
last job is finished. If it is not possible to do all the jobs, print -1 instead.

Limits
1 <= C <= 500
1 <= M <= 50
1 <= N <= 50
There are at most 20 buildings.

Problem Setter : ACM Team