#2106 FIVESTAR

1 s   128 MB  

Description

비어있는 높이 N, 너비 M의 격자 판이 있다(비어있는 공간은 ’.’로 표기한다.) 이러한 격자판에 ‘*****’가 새겨진 막대를 이용하여 입력받은 패턴을 재현할 수 있는지 없는지 판단하고, 가능 할 경우 사용되는 막대의 최소 개수를 알아내는 프로그램을 제작하고자 한다. 막대에 새겨진 한 글자와 격자 판의 한 칸의 크기는 일치한다.

막대는 격자 판 내에 놓여야 하며 수는 제한이 없다. 막대끼리 겹칠 수 있으며, 수직 혹은 수평으로만 놓을 수 있다.

아래와 같은 패턴이 입력되었을 경우 2번째 열에 수직으로 막대를 하나, 2번째 행에 두 번째 열에 수평으로 막대를 하나, 마지막으로 4번째 행 첫 번째 열에 수평으로 막대를 하나 놓게 되면 3개의 막대로 패턴을 완성시킬 수 있다.

. * . . . .
. * * * * *
. * . . . .
* * * * * .
. * . . . .

 

Input

입력의 첫 줄에는 테스트 케이스의 개수 T가 입력된다.

테스트 케이스의 첫줄에는 격자판의 높이 N, 너비 M이 입력된다(1 ≤ N ≤ 5, 1 ≤ M ≤ 10). 그 다음 줄부터 N × M 크기의 패턴이 입력된다. 비어있는 칸은 ‘.’로, 채워져야 하는 칸은 ‘*’로 표시한다.

Output

각 테스트 케이스에 대해 입력된 패턴을 만들 수 없을 경우  − 1을, 0개 이상의 “*****”가 새겨진 막대로 만들 수 있는 경우 사용되는 막대의 최소 개수를 한줄에 출력한다.

Sample Input

Sample Output

1
5 6
.*....
.*****
.*....
*****.
.*....
3

Source

20130912 - 인터넷 예선 대비 대회