Description

小芳有一块大小为R*C的矩形田园，里面的每个格子都种上了萝卜，每个萝卜都长得特别大，看上去都很健壮。这可惹来了邻居小肥的嫉妒，因为他种的萝卜个个都好像萎靡不振的样子。有天夜里，小肥偷偷潜入小芳的田园，在它的一些格子里放了一些害虫。第二天，小芳发现后，非常恼火，她连忙拿来一个里面装满药水的喷罐，想尽快除去这些害虫。但是她又不想喷到那些没遭殃的格子。每喷一次药水，在宽度上只能覆盖一个格子，但在长度上可覆盖到的格子数可由小芳自己任意设定，喷射方向只能横着或者竖着。现要你算算小芳最少需要喷几次药水才能杀完田园里的所有害虫，同时又保证不能喷洒到没有害虫的格子。

Input

输入包含多组测试数据。 每组测试数据的第一行包含两个整数R、C（1<=R<=30，1<=C<=30），分别表示格子的行数和列数。 接下来有R行，每行包含C个字符。 格子上的字符由''和'.'组成。若格子上的字符为''，则表明这个格子上有害虫。

Output

针对每组测试数据输出一行，这一行里包含一个整数，即最少需要喷药水的次数。

Sample

Input

1 4
.***
4 4
*.*.
.***
***.
..*.

Output

1
4

Source: z_y