Hyundai Mobis Special Prize 2

Interview

Time limit1sMemory limit1024 MB

Summary

Count how many times the word MOBIS can be read in an N by N letter grid, starting from any cell and moving in one of 8 directions.

Level: Easy2 of 10
Topics: Brute force, String matching
Solved: No attempts yet

Problem

Hyundai Mobis once again sponsors A.N.S.I., the club hosted by APC, to foster talented software developers. This year, Hyundai Mobis prepared a special prize for everyone who took part in APC 2024.

Hyundai Mobis prepared a grid of size $N \times N$ . Each cell contains one uppercase English letter. The special prize goes to the person who finds the most MOBIS in this grid. Finding MOBIS follows this rule:

Start at any cell in the grid and pick one of 8 directions: up, down, left, right, or one of the four diagonals. Read five letters in order along that direction. The combined five letters must be MOBIS.

Hyunbin wants to win the special prize by any means. Help Hyunbin find the maximum number of MOBIS that can be found in the given grid.

Input

The first line contains an integer $N$ . ( $1 \leq N \leq 100$ )

From the second line through line $N+1$ , the grid is given. Each line consists of $N$ uppercase English letters.

Output

Print the number of MOBIS that can be found in the given grid.

Examples2

Example 1

Input

9
SXXXSXXXS
XIXXIXXIX
XXBXBXBXX
XXXOOOXXX
SIBOMOBIS
XXXOOOXXX
XXBXBXBXX
XIXXIXXIX
SXXXSXXXS

Expected output

Example 2
Input
```
3
MOB
AOI
MUS
```
Expected output
```
0
```