I. Omar and Data Structures 1
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yehia gave Omar a square 2D array of size $$$N$$$ x $$$N$$$. He wants Omar to count the number of nodes in a Quad Tree built from this array.

Definition – Quad Tree

A Quad Tree is a tree built recursively as follows: (see Notes for visualization)

  • Each node represents a square submatrix.
  • If all elements in the submatrix are equal, the node is a leaf node.
  • Otherwise, the matrix is split equally into 4 quadrants (top-left, top-right, bottom-left, bottom-right), and each quadrant becomes a child node. This process continues recursively until all nodes are leaf nodes.

Your task is to determine the total number of nodes (both internal and leaf nodes) in the Quad Tree.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 512$$$, $$$N$$$ is guaranteed to be a power of $$$2$$$).

The next $$$N$$$ lines each contain $$$N$$$ integers $$$A[i][j]$$$ ($$$A[i][j]$$$ is either $$$0$$$ or $$$1$$$) — the elements of the 2D array.

Output

Print a single integer: the total number of nodes in the Quad Tree.

Examples
Input
4
0 1 1 1
1 1 1 0
0 0 0 1
0 0 0 1
Output
17
Input
2
0 0
0 0
Output
1
Input
8
0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0
0 1 1 0 0 0 1 1
1 0 1 1 1 1 0 1
0 0 0 1 0 0 0 0
1 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1
1 1 0 1 0 0 1 0
Output
77
Note

The tree formed for test case 1 is as follows

The second testcase will form only one node (root node) because it all has the same value.