On one horizontal or vertical line segment 2 On one horizontal, vertical, or diagonal line segment 9 On one line segment or two perpendicular line segments

Output Specification

The output will consist of a single non-negative integer \(H\) , representing the number of times the word is hidden in the grid.

Sample Input 1

MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

Sample Output 1

3

Explanation for Sample Output 1

The word MENU is hidden three times in the grid. Once horizontally, once vertically, and once diagonally as shown. Notice that a single letter can be used more than once.

Sample Input 2

NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E

Sample Output 2

4

Explanation of Sample Output 2

The word NATURE is hidden four times in the grid. Once diagonally, once vertically, and twice on perpendicular line segments.