Description

已知以下 4 种都是卖萌表情（空白的部分可以是任意字符。竖线是便于展示的分隔符，没有实际意义）：

^ ^ |  ^  | <  |  >
 v  | v v |  > | <
    |     | <  |  >

给出 n 行 m 列的字符矩阵，Bobo 希望找出互不重叠的卖萌表情数量的最大值。互不重叠的意思是每个字符只属于至多一个卖萌表情。

• 1 ≤ n, m ≤ 1000
• 矩阵只包含 ^, v, <, > 4 种字符。
• n × m 的和不超过 2 × 10⁶.

Input

输入文件包含多组数据，请处理到文件结束。

每组数据的第一行包含 2 个整数 n 和 m.

接下来 n 行的第 i 行包含长度为 m 的字符串，表示字符矩阵的第 i 行。

Output

对于每组数据输出 1 个整数表示互不重叠的卖萌表情数量的最大值。

2 4
^^^^
>vv<
2 4
vvvv
>^^<
4 2
v>
<>
<>
^>
3 4
^>^>
<v>v
>>>>

2
0
2
2

Hint

第一组样例中有 2 个第一种卖萌表情。

第四组样例中有 3 个卖萌表情，但是互不重叠的卖萌表情最多只有 2 个。