Fire!

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.

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.

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