beecrowd | 3355

Chess Pinhões

By Leandro Zatesko, Federal University of Technology of Paraná BR Brazil

Timelimit: 1

Carlinhos is a a 4-year-old boy who lives in Brazilian South Region and loves having pinhão, the regional typical delicacy, to eat as a winter snack. His mother, an expert chess player, was yesterday talking about chess openings with her friends from the women's chess club of their city. Carlinhos, listening to their conversation, understood that, in chess, the position of the pinhões, instead of pawns (peões, in Portuguese), is an important thing. So he took a chessboard belonging to his mother and then placed some pinhões at cells that he considered to be strategic.

A few hours later, Carlinhos's mother found the chessboard and now, for fun, she wants to eliminate all the pinhões using a queen. The first step is to find out which free cell to first place the queen so that it attacks the greatest number of pinhões.

Preliminaries. In chess, a piece is said to be attacking a cell if the piece can be moved to that cell in a single movement. The queen is the piece that, in a single movement, can be moved on a straight line through any number of contiguously free cells in exactly one of any of the eight directions defined by the rows, columns, and diagonals which intersect the queen's cell in the board. Therefore, the queen can move to, but cannot move through, a cell occupied by a pinhão. In the board depicted in the figure below, the queen attacks five pinhões. However, in this board it is possible to place the queen at a free cell so that eight pinhões are attacked.



The first line of the input consists of a single integer N (2 ≤ N ≤ 103), representing the number of rows and columns of the chessboard. Then follow N lines, each containing exactly N characters, each of which can be a '.', representing a free cell in the board, or a 'P', representing a pinhão. It is guaranteed that there is at least one pinhão and at least one free cell in the board.


Print the greatest number of pinhões which is possible to attack by placing a queen at some free cell in the board.

Input Samples Output Samples