There is war and ashu needs hog riders for the fight. The area on which hog riders live is a N X N square matrix. If A[i][j] = 1 it means a hog rider is standing at that place and if it is 0 then the place is empty. To call them ashu stands on any tile on which a hog is present and makes that particular hog shout loud. All the hog riders standing adjacent to the tile where one shouts listen and they also start shouting so again those hogs which are connected to them also starts shouting and calling others for war. So you have to output the best position where ashu should go so that maximum hog riders will attend the war.
Adjacent to a tile means tiles which lie on above,below,left and right of that tile. Ashu can't stand on a tile which is empty or else he has to make the noise which is not possible

Input
First line contains N as input which is size of matrix. Next N lines contain N integers as 0 or 1 indicating gaps and hogs

Output
You have to output the maximum number of hogs that can be called

Scoring
1≤ N ≤ 10 20pts
1≤ N ≤ 100 40pts
1≤ N ≤ 1000 40pts