Escape Sadland

The year is 2060. Global warming is getting so bad that it's causing floods everywhere, especially in Sadland. Barr the bear is stuck in Sadland and he needs to escape before the flood drowns him!

Fortunately, technology is so advanced now that it's possible to teleport from one place to another by entering a teleporter. And even more fortunately, there is a magical teleporter in Sadland that can teleport anyone to Happyland, which is free of floods! Obviously Barr wants to get to this teleporter before he drowns in the flood. However, Barr is also a very lazy bear taking his afternoon nap and would like to sleep for as long as possible before making his way to the teleporter. Your job is to help him find out the maximum amount of time he can sleep and still escape from Sadland in time.

Sadland is represented by a grid of N by N unit cells whose sides are parallel to the north-south and east-west directions. Some of the cells will have holes, one cell will be the magical teleporter, and the rest will be grassy cells. When Barr moves, he can make at most S steps per minute. A step is basically a move onto an adjacent grassy cell to the north, south, east, or west (he cannot walk into holes). Initially, Barr will be in his home on a grassy cell, and the floods will occupy several grassy cells. During each minute from this time onwards, the following events happen in order:

• If Barr is still sleeping, he decides whether to wake up and leave or not. If he continues sleeping, he does not move for a whole minute. Otherwise, he leaves immediately and takes up to S steps.
• The floods then start to expand their territory. Specifically, each cell that is flooded will cause all adjacent grassy cells to be flooded too. Of course, a cell with a hole will not be flooded, since the water will just drain into the hole. Furthermore, the cell with the teleporter will never be flooded due to its powerful magic.

Neither the floods nor Barr can go outside Sadland. Also note that Barr can only sleep for an integer number of minutes. Barr will drown in the floods if at any point in time Barr finds himself in a flooded cell.

Input

The first line contains integers N (1 ≤ N ≤ 800) and S (1 ≤ S ≤ 1,000) separated by a space.

The next N lines represent the Sadland grid. Each of these lines contains N characters, each representing a unit cell of the grid. H denotes a hole; G denotes a grassy cell; B denotes Barr's home, which is also on a grassy cell; T denotes the cell with the teleporter; and F denotes a flooded cell.

NOTE: It is guaranteed that the map will contain exactly one letter B, exactly one letter T and at least one letter F. It is also guaranteed that there is a sequence of adjacent letters G that connects Barr to the teleporter, as well as a sequence of adjacent letters G that connects at least one flooded cell to Barr's home (i.e., to Barr's initial location). These sequences might be as short as length zero, in case the teleporter or a flooded cell is adjacent to Barr's initial location. Also, note that the cell with the teleporter cannot be flooded.

Output

On the first and only line write a single integer: the maximum possible number of minutes Barr can sleep while still being able to escape Sadland safely. If Barr cannot possibly reach the teleporter before he drowns in a flood, output -1 instead.

Sample Input 1

7 3
HHHHHHH
HGGGGGH
HGGGGGH
BGGGGGT
HGGGGGH
HGGGGGH
HFFFFFH

Sample Output 1

1

Explanation for Sample Output 1

After sleeping for one minute, Barr can take the shortest path directly to the right and he will reach the teleporter in another two minutes, safe from the floods.

Sample Input 2

7 3
HHHHHHH
HGGGGGH
HGGGGGH
BGGGGGT
HGGGGGH
HGGGGGH
HGFFGGH

Sample Output 2

2

Explanation for Sample Output 2

After sleeping for two minutes, Barr can take steps east, north, east during the third minute, then steps east, east, east during the fourth minute and steps south, east during the fifth minute.