Binbin is a clever boy who likes to wear a skirt. One day, he saw some beautiful skirts on Taobao, but he had not enough money, which made him sad.

In order to make Binbin feel happy again, his's friend Xu1024 gave him a treasure map. The treasure map is composed of three characters:
'.', '#', '$'.

• Character '.' indicates that this position is empty and passable;
• Character '#' indicates that this position is blocked by a stone and not passable;
• Character '$' indicates that this position has 1 coin on it and is passable.

The locations outside the treasure map are all empty and passable.
Binbin can move up, down, left, and right, but not at an angle.
Firstly, Binbin can choose any grid as starting point.
Because Binbin wants to wear a skirt so much, he has a chance to teleport to a certain grid as another starting point.
Binbin wants to know how many coins he could eventually collect to buy skirts.
Can you help him?

The first line of each group contains two numbers $N$ and $M(1≤N, M≤500)$, representing the number of rows and the number of columns of treasure map.
Then there are next $N$ lines, each line contains $M$ characters. which describe the treasure map.

Ouput a integer representing the maxinum coin(s) Binbin would collect.

In the first case, Binbin can start at point $(1,1)$ so he can collect $2$ coins.
Then Binbin can teleport to point $(3,2)$ so he can collect $1$ coin.
Finally, Binbin would collect $3$ coins.

In the second case, Binbin can start at point $(1,1)$ so he can collect $2$ coins.
Then Binbin can teleport to point $(3,2)$ so he can collect $1$ coin.
Finally, Binbin would collect $3$ coins.