ROR game is a game where players are divided into two teams and a team wins if they destroy the camp of the other team first. Therefore, each team's goal is to go to the other team's camp as quickly as possible.

You are going to play the game as a member of one side. Following shows an example where in a 5 x 5 map, your character is placed in (row: 1, column: 1) and camp of the other team is placed in (row: 5, column: 5).

In the above figure, you cannot move through black space, while you can move freely through white spaces. The character moves by one space at once in East, West, South, and North directions. Also the character cannot go out of the map.
Following example shows 2 ways to move the character to the other team's camp.

• In the first method, the character arrives at the camp of the other team through 11 spaces.

• In the second method, the character arrives at the camp of the other team through 15 spaces.

Therefore, the first way is the fastest way to get to the other team's camp.
If the other team builds walls around the camp, you can not move to their camp. For example, in the following case, your character cannot arrive at the other team's camp.

Given the status of game map maps as a parameter, write a function solution to return the minimum number of moves required for your character to arrive at the camp of the other team. But, return -1 when there is no way to reach their camp.

Constraints

• maps is a 2-dimensional array containing the status of the game map with n x m size. n and m are natural number between 1 and 100.
• n and m may be either the same or different each other, but there is no case where both are given as 1.
• maps consists of 0 and 1 only, which indicates the space with wall and without wall, respectively.
• Initially, the character is located at the left top of the game map (1, 1), and the camp of the other team is at the right bottom of the game map (n, m).

Examples

Example #1
Data is given as follows.

The shortest path to move your character to the other team's camp is as follows.

Therefore, since the character passes through total 11 spaces, return 11.

Example #2
It is the same with an example in the problem statement where there is no way to reach the camp of the other team. Hence return -1.