10050_AnEasyPuz

Wddpdh find an interesting mini-game in the BBS of WHU, called "An easy PUZ". It's a 6 × 6 chess board and each cell has a number in the range of 0 and 3 ( it can be 0, 1, 2 or 3 ). Each time you can choose a number A(i, j) in i-th row and j-th column, then the number A(i, j) and the numbers around it ( A(i-1, j), A(i+1, j), A(i, j-1), A(i, j+1), sometimes there may just be 2 or 3 numbers.) will minus 1 ( 3 to 2, 2 to 1, 1 to 0, 0 to 3 ).

You can do it finite times. The goal is to make all numbers become 0. Wddpdh now come up with an extended problem about it. He will give you a number N ( 3 ≤ N ≤ 6 ) indicate the size of the board. You should tell him the minimum steps to reach the goal.

The input consists of multiple test cases. For each test case, it contains a positive integer N ( 3 ≤ N ≤ 6 ). N lines follow, each line contains N columns indicating the each number in the chess board.

For each test case, output minimum steps to reach the goal. If you can't reach the goal, output -1 instead.

3
1 1 0
1 0 1
0 1 1
3
2 3 1
2 2 1
0 1 0

2
3