Background

Description

⻛国和⽻国正在进⾏⼀场战争！
⽻国是⼀个岛国，我们把⽻国的地图分成n⾏m列个⼩的格⼦，有的格⼦是海，有的格⼦是⽻国的⼟地。⽻国的国⼟是连通的（如果两个格⼦共享⼀条边，我们称这两个格⼦连通，并且这两个格⼦相互可达），即从⽻国的任意⼟地都可以到达其另⼀块⼟地。
现在，⻛国出于战略考虑，想使⽤⼟之魔法将⽻国的某些⼟地移⾛，这样那些格⼦就会变成⼤海，⻛国的最终⽬的是使得⽻国不再连通，现在，⻛国国王想请教你，最少需要⽤⼟之魔法移⾛多少块⽻国的⼟地移⾛，使得⽻国不再连通。

Format

Input

第1⾏，包含1个整数：T，表⽰测试组数。
对于每组测试数据：
第1⾏，包含2个整数：n, m。
接下来n⾏，每⾏包含m个字符，其中第i⾏第j列的字符为，如果是"."，表⽰该位置是海洋，如果是"#"，表⽰该位置是⽻国的⼟地。

Output

对于每组测试数据，输出1⾏，包含1个整数：c，表⽰最少需要移⾛的⼟地数，如果⽆论如何都不能达到⽬的，输出-1.

Sample

Input

2
3 3
...
###
...
3 3
...
##.
...

Output

1
-1

Explanation

对于第1组数据，可以把(2,2)位置的⼟地移⾛。
对于第2组数据，⽆论如何都不可能把⽻国的⼟地变成不连通。

Limitation

对于30%的数据，1 ≤ n, m ≤ 5；
对于50%的数据，1 ≤ n, m ≤ 50；
对于100%的数据，1 ≤ n, m ≤ 300, 1 ≤ T ≤ 10。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST