Georg has a new profession: he now works in a candy factory. The job is way more boring than it sounds: he is responsible for quality assurance. And that means taking a box of candies, counting them and checking that none are missing. Help poor Georg! Write a program that will do the job for him.
You will be given a matrix with r rows and c columns. This matrix represents the top view of a box of candies. The matrix will only contain the following characters:
There are exactly two ways how a whole piece of candy looks like:
1. >o< 2. v
Whenever you see three characters arranged in this way, you see a whole piece of candy.
For the given matrix count the number of whole pieces of candy it contains.
In the easy data set the box will only contain whole pieces of candy and nothing else.
In the hard data set the box can also contain fragment of candies: characters o<>v^ that don’t belong to
any whole candy. To make your life easier, you may assume that the following conﬁguration will never appear in
the hard data set:
The ﬁrst line of the input ﬁle contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
The ﬁrst line of each test case contains two integers r and c (1 ≤ r,c ≤ 400): the dimensions of the matrix. Each of the next r lines contains one row of the matrix: c characters from the set “.o<>v^”. (Their ASCII values are 46, 111, 60, 62, 118, and 94.)
For each test case, output a single line with one integer – the number of whole candies in the box.
There are three whole candies: in the ﬁrst row, in the last row, and in the ﬁrst column.