描述

编程实现： 有一个N行N列的网格，网格里的每个格子都有一个字母，每个字母只能是p、y、t、h、o、n 中的字母。 一台机器人按照以下规则移动： 1、起始位置可以选择网格中任意一个格子，起始位置的字母不一定为p； 2、每次只能向上下左右相邻的任意一个格子移动一格，并且经过的格子不能再次经过； 3、每次移动的格子中的字母必须按照以下环形的顺序，如下图所示：

例如：当前字母为t，那么移动的下一个格子中的字母必须为h。 给定N行N列的网格，请计算机器人最多可以经过多少个字母。 例如：N=4，4行4列的网格中的字母如左图，可经过最多字母的移动路径如右图：

以第三行第二列的h作为起始位置，按照h -> o -> n -> p -> y -> t -> h的顺序移动，机器人经过的字母最多，可以经过7个字母。

输入输出数据

输入

第一行输入一个整数N （$2≤N≤50$），表示网格的行数和列数

接下来输入N行，每行N 个字母，每个字母只能是p、y、t、h、o、n 中的字母，字母之间以一个空格隔开

输出

输出一个整数，表示机器人最多可以经过多少个字母

样例

4
y n p p
t o y t
n h p h
n h o t

7