Big Square

No attempts yetTime limit1sMemory limit128 MB

Problem

Farmer John's cows are competing against Farmer Bob's cows. On a field marked with an $N \times N$ grid of points ($2 \le N \le 100$), every cow of both herds stands on a distinct grid point; no two cows may share a point. Each herd wants to form the largest possible square (its sides need not be parallel to the grid lines) whose four corners are all cows of that herd.

Every cow has already been placed except for Farmer John's cow Bessie. Bessie must be placed on one currently empty grid point. Determine the area of the largest square that Farmer John's cows can form after Bessie is placed. (The largest square does not have to include Bessie herself.)

Input

  • Line 1: a single integer $N$.
  • Lines 2 through $N+1$: line $i+1$ contains $N$ characters describing row $i$ of the field. Each character is J for a Farmer John cow, B for a Farmer Bob cow, or * for an empty grid point. There is always at least one empty grid point.

Output

  • Line 1: the area of the largest square Farmer John's cows can form, or 0 if no square can be formed.

Hint

In the sample, if Bessie could stand on the grid point occupied by Farmer Bob's cow, a square of area 8 could be formed. But two cows may not share a grid point, so the best Bessie can do is stand in row 3, column 3 to complete the top-left square, which has area 4.