Minimum Days to Infect All Plants

In this problem, you are given a 2D grid that represents a farm. Each cell in the grid contains either a healthy plant, represented by 'H', or an infected plant, represented by 'I'. Infection spreads from an infected plant to any adjacent healthy plant in four directions (up, down, left, right) in one day. Your task is to compute the minimum number of days required to infect all healthy plants. If it is impossible to infect all plants, output (-1).

Formally, let (farm) be an (M \times N) grid. Initially, infected cells are given. At each step, every infected cell infects its adjacent healthy cells. The process continues until either all plants are infected or no further infection is possible.

inputFormat

The input is read from standard input and has the following format:

• The first line contains a single integer (T) denoting the number of test cases.
  
• For each test case:
  
  • The first line contains two integers (M) and (N), which represent the number of rows and columns of the farm respectively.
    
  • The next (M) lines each contain a string of length (N) representing the row of the farm, where each character is either 'H' or 'I'.

outputFormat

For each test case, output a single integer on a new line. This integer is the minimum number of days required to infect all healthy plants, or (-1) if it is impossible.## sample

2
3 3
HHH
HIH
HHH
3 3
HHH
HHH
HHH

2
-1