Fire!

Interview

Time limit1sMemory limit256 MB

Summary

Given a grid with walls, one starting cell, and fire cells that spread each second, find the earliest time the person can step off the map.

Level: Medium6 of 10
Topics: BFS, Graph, Queue, Simulation
Solved: No attempts yet

Problem

Sanggeun is trapped in a building made up of empty spaces and walls. A fire has broken out in parts of the building, and Sanggeun is trying to escape.

Every second, the fire spreads from each burning cell to the empty cells directly adjacent to it (up, down, left, right). Fire cannot spread onto walls. Each second Sanggeun can move to one of the four adjacent cells. He cannot pass through walls, and he cannot move into a cell that is already on fire or a cell that the fire is spreading into at that very second. However, he may move out of his current cell at the same moment the fire reaches it.

Sanggeun escapes the instant he steps off the edge of the map. Given the map of the building, find the shortest time Sanggeun needs to escape.

Input

The first line contains the number of test cases, at most 100.

The first line of each test case contains the width $w$ and the height $h$ of the map. ( $1 \le w, h \le 1000$ )

Each of the next $h$ lines contains $w$ characters describing the map, where each character means:

. : empty space
# : wall
@ : Sanggeun's starting position
* : fire

There is exactly one @ in each map.

Output

For each test case, print the shortest time for Sanggeun to escape the building on its own line. If escaping is impossible, print IMPOSSIBLE.

Examples3

Example 1

Input

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

Expected output

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

Example 2
Input
```
1
3 3
...
.@.
...
```
Expected output
```
2
```
Example 3
Input
```
1
5 5
.....
.....
..@..
.....
....*
```
Expected output
```
3
```