You are given a graph in the form of a matrix of size \( N * M\) containing '#' and '.'.All the cells containing '#' are nodes of the graph and two nodes are considered to be connected if they are present at the top, left, right, or bottom of each other. Initially, the graph is connected.

Write a program to determine the minimum number of nodes that need to be deleted from the graph in order to break it into two unconnected graphs.

Input format

• First line: T (number of test cases)
• First line in each test case: Two space-separated integers N and M
• Next N lines in each test case: M space-separated characters, each '.' or '#' as described in the statement.

Output format

For each test case, print the minimum number of nodes that need to be deleted from the graph in order to break it into two unconnected graphs. If it is not possible to divide the graph into two parts, print -1.

Constraints

\(1 ≤ T ≤ 10\)
\( 1 ≤ N,M ≤ 50 \)