Bob is lost in the city of Cownogor. It is a great problem for him now. People in Cownogor speaks Cow language (For more see: https://esolangs.org/wiki/COW). As an outsider he is not familiar with this language. So he cannot ask anyone for direction. Moreover he lost his phone. But he knows that he can go back to his city if he can get out of this city anyway.

Cownogor can be represented with a grid of height and width w. Each cell of the grid represents a place of the city. Each cell is connected with all of its 8 adjacent cells (if there) with a path. One can go from a cell to another cell in one second. He needs gij money to visit the cell of ith row (from left) and jth column (from top). Bob believes that straight path is the only way to success. So he follows straight paths only and avoid all other paths. He visits a cell if it is adjacent to his current cell and has a straight path between them. He considers a path is straight if it connects two adjacent cells sharing at least one side.

Now he is in the cell of ith row (from left) and jth column (from top). Can you determine the minimum time that he must travel before he can get out of this city? You are given a grid. Each line contains integers gi,j (0<=gij<=9)-The cost to visit this cell. There are no space between numbers. Bob's Current position is in the cell which costs 0 and no other cell costs 0. Each test case except the last one is followed by an empty line. For each test case your output should be a line with case number followed by the answer.