You are planning a hike in the Peneda-Gerês National Park in the north of Portugal. The park takes its name from two of its highest peaks: Peneda (1340 m) and Gerês (1545 m).

For this problem, the park is modelled as an infinite plane, where each position $$$(x, y)$$$, with $$$x, y$$$ being integers, has a specific altitude. The altitudes are defined by an $$$n \times n$$$ matrix $$$h$$$, which repeats periodically across the plane. Specifically, for any integers $$$a, b$$$ and $$$0 \leq x, y \lt n$$$, the altitude at $$$(x + an, y + bn)$$$ is $$$h[x][y]$$$.

When you are at position $$$(x, y)$$$, you can move to any of the four adjacent positions: $$$(x, y+1)$$$, $$$(x+1, y)$$$, $$$(x, y-1)$$$, or $$$(x-1, y)$$$. The time required to move between two adjacent positions is $$$1 + \lvert \text{alt}_1 - \text{alt}_2 \rvert$$$, where $$$\text{alt}_1$$$ and $$$\text{alt}_2$$$ are the altitudes of the current and destination positions, respectively.

Initially, your position is $$$(0, 0)$$$. Compute the number of distinct positions you can reach within $$$10^{20}$$$ seconds. Your answer will be considered correct if its relative error is less than $$$10^{-6}$$$.

Input

The first line contains an integer $$$n$$$ ($$$2\le n\le 20$$$)—the size of the matrix describing the altitudes.

The following $$$n$$$ lines contain $$$n$$$ integers each. The $$$(j+1)$$$-th number on the $$$(i+1)$$$-th of these lines is $$$h[i][j]$$$ ($$$0\le h[i][j] \le 1545$$$)—the altitude of the position $$$(i, j)$$$.

Output

Print the number of distinct positions you can reach within $$$10^{20}$$$ seconds. Your answer will be considered correct if its relative error is less than $$$10^{-6}$$$.

Note

In the first sample, every position of the Peneda-Gerês National Park has an altitude of $$$3$$$. Therefore, the time required to move between two adjacent positions is always equal to $$$1$$$ second.

In this case, one can show that a position $$$(x, y)$$$ is reachable within $$$10^{20}$$$ seconds if and only if $$$|x|+|y| \le 10^{20}$$$. One can compute that there exist $$$20\,000\,000\,000\,000\,000\,000\,200\,000\,000\,000\,000\,000\,001$$$ reachable positions and this number is approximated by $$$2\cdot 10^{40}$$$ with a relative error smaller than $$$10^{-6}$$$. The sample output shows $$$2\cdot 10^{40}$$$ as correct answer, but also the exact number of reachable positions would be a correct answer.

In the second sample, every position $$$(x, y)$$$ of the Peneda-Gerês National Park with $$$x-1$$$ and $$$y-1$$$ divisible by $$$3$$$ has an altitude of $$$1545$$$, while all the other positions have an altitude of $$$0$$$. For example, the time required to move between $$$(4, 10)$$$ and $$$(4, 9)$$$ is $$$1546$$$, while the time required to move between $$$(3, 2)$$$ and $$$(4, 2)$$$ is $$$1$$$.

The positions reachable in $$$2$$$ seconds are all positions $$$(x, y)$$$ with $$$|x|+|y|\le 2$$$ apart from $$$(1, 1)$$$ (which is on the peak). One can compute that there exist $$$19\,999\,999\,999\,999\,999\,931\,533\,333\,333\,333\,333\,863\,441$$$ reachable positions in $$$10^{20}$$$ seconds and this number is approximated by $$$2\cdot 10^{40}$$$ with a relative error smaller than $$$10^{-6}$$$. The sample output shows $$$2\cdot 10^{40}$$$ as correct answer, but also the exact number of reachable positions would be a correct answer.

A Very Long Hike

Examples