给一个N * M的棋盘，棋盘上的有些格子被打上了标记。现在需要在其中放置尽量少的皇后，使得所有被打上标记的格子至少被某一个皇后攻击或占据到。皇后之间可以互相攻击。

输入最多15组数据。
每组数据第一行包含两个整数N和M(1 < N, M < 10)，以下为一个N行M列的棋盘，其中打上标记的格子用‘X’表示，其它格子用‘.’表示。
输入以一个0结尾

对于每组数据，输出一个数表示最少需要使用的皇后数目。