The following 4 patterns are considered "cute faces" (blank spaces can be any character; vertical bars are separators for display purposes and have no actual meaning):

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

Given an $n \times m$ character matrix, Bobo wants to find the maximum number of non-overlapping cute faces. Non-overlapping means that each character belongs to at most one cute face.

Input

The input contains multiple test cases. Process until the end of the file.

The first line of each test case contains two integers $n$ and $m$.

The next $n$ lines, the $i$-th line contains a string of length $m$, representing the $i$-th row of the character matrix.

Output

For each test case, output a single integer representing the maximum number of non-overlapping cute faces.

Constraints

• $1 \leq n, m \leq 1000$
• The matrix contains only the 4 characters ^, v, <, >.
• The sum of $n \times m$ does not exceed $2 \times 10^6$.

Examples

Input 1

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

Output 1

2
0
2
2

Note

In the first example, there are 2 of the first type of cute face.

In the fourth example, there are 3 cute faces in total, but the maximum number of non-overlapping cute faces is 2.