CubeCraft is a game consisting entirely of cubes (or voxels) having a side length equal to , and each voxel’s vertices have integer coordinates. After playing this game for a while, Jessie is eager to create something impressive so she decides to build a lighthouse.

First, Jessie decides she wants the lighthouse to have a round base; because there is no such thing as a perfect circle in a cubic world, she defines a circle with integer radius to be the set of all cubes having centers with a Euclidean distance to the center of the circle (which coincides with the center of some cube) . Because is the Euclidean distance between the center points of two cubes, the value of for a single cube is .

Next, she chooses an grid for the base of the lighthouse. This presents some difficulty for Jessie because there are landscape features (e.g., rocks, trees, etc.) in the grid. She doesn’t want to change the landscape and cannot build over it, so she must find the maximum radius of any circle she can place inside the grid’s free space (i.e., where no landscape obstructions are contained within the confines of the circle). Note that circle have to be placed completely inside the grid, i.e. there should be no points with euclidean distance to the center outside the grid.

Given and the landscape features of Jessie’s grid, find and print the maximum possible value of .

**Input Format**

The first line contains an integer, , denoting the side dimensions of the grid where Jessie wants to build the lighthouse.

Each line of the subsequent lines contains a string of characters describing the landscape features of row in the grid. A `.`

indicates that is empty, and a `*`

indicates that it’s obstructed.

**Constraints**

- It is guaranteed that the grid contains at least one empty cell (i.e., input will always contain at least one
`.`

character).

**Output Format**

Print the value of denoting the maximum integer radius of the circle Jessie can place inside the grid’s free space (recall that may be ).

**Sample Input 0**

```
9
*********
****.****
**.....**
**.....**
*.......*
**.....**
**.....**
****.****
*********
```

**Sample Output 0**

`3`

**Solution**

```
import java.util.Scanner;
public class Circle {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
char a[][] = new char[t][t];
if (t <= 2) {
System.out.println(0);
} else {
int r = 0;
if (t % 2 == 0)
r = (t / 2) - 1;
else
r = t / 2;
scan.nextLine();
int k = 0;
for (int i = 0; i < t; i++) {
String str = scan.nextLine();
a[k] = str.toCharArray();
k++;
}
int finalrad = r;
boolean b = false;
for (int z = r; z > 0; z--) {
if (b == true)
break;
// System.out.println("radisu z = "+z);
for (int i = z; i < t - z; i++) {
if (b == true)
break;
for (int j = z; j < t - z; j++) {
// System.out.println("i "+i + " j "+j);
b = checkCircle(a, t, z, i, j);
// System.out.println("b "+b + "z "+ z);
if (b == true) {
// System.out.println("b "+b);
finalrad = z;
break;
}
}
}
}
if (b == true)
System.out.println(finalrad);
else
System.out.println(0);
}
}
}
/*
9
*********
****.****
**.....**
**.....**
*.......*
**.....**
**.....**
****.****
*********
output --> 3
*/
```