Cows are addicted to word puzzles. For example, like this
USOPEN
OOMABO
MOOMXO
PQMROM
Like cows, they are only interested in the single word "MOO", which can appear in many places horizontally, vertically, or diagonally. The example above contains 6 such words.
Farmer John is also a fan of such puzzles. Because the cows don't want him to solve the puzzle before the cows, they encrypt the puzzle using a substitution cipher that replaces each letter of the alphabet with some different letter. For example, A can be replaced by the letter X, B by the letter A, and so on. No letter is replaced by itself, and no two letters are replaced by the same letter (otherwise the transcript may become ambiguous).
Unfortunately, the cows have lost their encryption table and are now unable to decipher their puzzle. Please help them determine the maximum number of MOO words that can exist for their puzzle by choosing the appropriate encryption table
INPUT FORMAT :
The first line of input contains N and M describing the number of rows and columns in the puzzle (both no more than 50). Each of the following N lines contains M characters describing one line of the encrypted puzzle. Each character is a capital latin letter in the range A..Z.
OUTPUT FORMAT :
Print the maximum possible number of MOO words contained in the puzzle, if it is decrypted with the appropriate encryption table.
| Input |
Output |
|
4 6
TAMHGI
MMQVWM
QMMQSM
HBQUMQ
|
6 |
Explanation
This is the puzzle given at the beginning of the problem, where "M" and "O" were replaced by "Q" and "M" respectively.