Boggle

An English teacher showed his students a simple word game called Boggle. You will be given a square grid of uppercase letters embedded with words. You can find an embedded word by locating the first letter of the word in the grid then determining if the second letter is adjacent to the first letter, then if the third letter is adjacent to the second one, and so on until the whole word is spelt. Diagonally adjacent letters are also adjacent.

For example,


M A A A A
A O A A A
A A U A A
A A A S A
A A A A E


in the grid above, the word "MOUSE" is embedded.

You may use cells multiple times if you wish. For example,


K I A A A
A C A A A
A A A A A
A A A A A
A A A A A


in the grid above, the word "KICK" is embedded even though you went from K to I to C then back to K.

You may not use the same cell twice in a row, though. For example,


B A N E D
X X X X X
X X X X X
X X X X X
X X X X X


in this grid, you may be tempted to make the word "BANNED" by using "N" twice in a row, but that is not allowed.


Your task is to find how many times a certain word appears in a given boggle grid.


Input Specification


The first line will contain N (1 ≤ N ≤ 20). The next N lines contain N space-separated uppercase characters.

The word to find is contained on a line after the grid. This word will be no longer than 10 characters long.


Output Specification


Print one integer: the number of times the specified word is contained in the boggle grid.


Sample Input 1


5
C X X X C
A X X X A
T X X X T
X X X X X
X X X X X
CAT


Output for Sample Input 1


2


Explanation for Sample Case 1: The word "CAT" is contained in the grid twice. Once on the left side and once on the right


Sample Input 2


5
B O G L E
X X X X X
X X X X X
X X X X X
X X X X X
BOGGLE


Output for Sample Input 2


0
Comments
  • There are no comments.