Problem B
Wrapping Trees

After last year’s spectacular failure, the Alberta Christmas Paraphernalia Company (ACPC) is getting an early start on their Christmas tree business this year. With all the extra time they have to prepare, the plan is to use some algorithmic methods to optimize their profits.

The ACPC would like to wrap a single piece of string around each tree so that they can tightly pack them into the warehouse. The tree supplier has kindly sent you a specification of the shapes of the trees. The cross section of the tree that you want to wrap the string around can be represented in compressed form by an $n$ by $n$ binary image, where each pixel corresponds to a $1$ cm by $1$ cm region of the tree. Unfortunately, as trees are very complicated shapes, it would take an infinite amount of time for you to download the complete uncompressed image of a tree. Luckily, the trees are of premium quality and thus have a very nice recursive structure. The full uncompressed image of the tree can be computed by recursively replacing every 1 pixel in the compressed image with a scaled down copy of the entire image an infinite number of times. Note that the dimensions of the full uncompressed image are still $n$ cm by $n$ cm, the same as the compressed image.

Given a compressed specification of a tree, your task is to find the shortest possible length of string (in centimeters) that can wrap completely around the perimeter of all 1 pixels in the corresponding uncompressed tree.

Figure 1: Illustration of sample input $3$. The compressed tree is given on the left. The second image is the tree after the first decompression step. After an infinite number of steps, we arrive at the final image on the right. The shortest possible string that encloses the uncompressed image is illustrated in red.

Input

The first line of input will contain an integer $n$ denoting the both the height and width of the compressed image in centimeters. You may assume that $1\le n\le 10^3$. The following $n$ lines will contain $n$ characters. Each character will be either a 0 or 1 describing the pixels of the compressed image.

Output

Output the smallest possible length of string that can completely enclose all points in the uncompressed tree corresponding to the given compressed tree. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-5}$.

1
1

4

3
000
111
000

6

5
10100
00101
00111
01100
00111

17.2656990001