The holidays have just ended so Jiahai is bored. So he decides to play reversi against himself to relief himself of his boredom while appearing interested in the lesson at the same time. It went very well for a day, until Jiahai realised that since Jiahai's playing against himself, Jiahai would know all the moves Jiahai would play before Jiahai moves. To counter this problem, he's asking your help to write a program to play against Jiahai. The program should always play a piece such that the resultant board immediately after its move would have the most number of its pieces.
Help Jiahai write a program which would find the move it could play which would give the highest number of the its remaining pieces!
The first line of input will consist of 1 integer, N. N denotes the length of the square board. N will be a positive integer not exceeding 20.
The following N lines will consist of a string of length N. Each character in the string denotes the piece at that position. '.' refer to a blank spot, 'J' refer to Jiahai's pieces, and 'P' refer to the program's own pieces
print one number, the number of remaining pieces belonging to the program after the program makes its move.
Explanation of Sample Output
putting the piece at the center of the board would flip 5 surrounding pieces.
resulting in this: (using a star to denote the piece which the program just placed)
an answer which would come close would flip 4 pieces, resulting in this:
do note that the piece which the program just played would also count towards the final answer.