You are playing a game on a grid of size \(N \times M\). The game has the following rules:

• The grid contains cells that the player can move to. These are denoted by a period (.)
• The grid contains cells that the player cannot move to. These are denoted by an asterisk (*)
• The player starts on the cell marked with a V.
• The player has to reach the cell marked with an H.

Write a program to find the path which has the minimum number of changes in direction. Print the number of times that the player needs to turn on the path

Input format

• First line: N and M
• Next N lines: M characters (denoting the cells of the grid)

Output format

Print the minimum number of times that the player needs to turn on the required path. If no path exists, print -1.

Constraints

\(1 ≤ N, M ≤ 10^{3}\)