Description

给一个大三角形,里面黑的三角形是被剪掉了的,需要在剩下的白色区域中找出一个最大的三角形区域

Input

输入包括几组关于大三角形样子的描述 每一组的第一行是一个整数N(1 <= N <= 1000)表示下面要描述的大三角形的高度 接下来的 N 行将用许多字符模拟出大三角形的样子,其中用“X”表示被剪掉的小三角形(即上图中的黑三角形) 用“O”表示 白色区域,每行字符个数从(2N-1)到1递减 如果组首为0,则表示结束

Output

每行输出一个数,表示剩下部分所能得到的最大的倒三角形的面积

Sample Input

5 XOXXOOOOX OOOOOXO OOOXO OXO O 0

Sample Output

9

Source

经典问题