In a given 2D binary array grid, there are two islands. Now, we may change 0s to 1s so as to connect the two islands together to form 1 island. Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Input Format
First line contains an integer n. Each of next n lines contain n numbers containing either 0 or 1.
Output Format
Return the smallest number of 0s that must be flipped.
Constraints
1<= n <= 1000
Example
Input
3 0 1 0 0 0 0 1 1 1
Output
1