题目背景

小核桃挑选了一部分健胃消食片，一不小心手滑，打翻了。

题目描述

健胃消食片打翻了，散落在桌子上。现在需要找到一对平行线(可以是横着，竖着)，使得这两条平行线之间的区域中，正面向上的健胃消食片数量最多且不包含反面向上的健胃消食片，并且这两条平行线不经过任何健胃消食片。

输入输出描述

输入

第一行一个正整数n，代表 $n \times n$的范围。 接下来n行，每行n个字符，以空格隔开。表示健胃消食片的正反面情况。

输出

一个正整数，代表某两条平行线之间的区域中，最多的正面向上的健胃消食片数量

样例

3
u u d
u u d
u u u

6

样例说明

红色的两条平行线包含正面向上的健胃消食片最多。

数据规模与约定

对于100%的数据，保证 $1 \leq n \leq 100$ 。 所有数据均保证正确。