import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Cell { int x, y; int oldDist; public Cell( int a, int b, int od ){ x = a; y = b; oldDist = od; } } public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // your code goes here int[][]nm = new int[n+1][n+1]; for( int i=1; i list = new LinkedList<>(); list.add( new Cell(1,1,-1) ); while( !list.isEmpty() ) { Cell p = list.remove(); if( p.x <= 0 || p.x > n || p.y <= 0 || p.y > n ) continue; if( visited[p.x][p.y] ) continue; dist[p.x][p.y] = p.oldDist + 1; if( p.x == n && p.y == n ) { nm[i][j] = dist[p.x][p.y]; nm[j][i] = dist[p.x][p.y]; list.clear(); //stop search... continue; } visited[p.x][p.y] = true; list.add( new Cell(p.x+i, p.y+j, dist[p.x][p.y])); list.add( new Cell(p.x-i, p.y+j, dist[p.x][p.y])); list.add( new Cell(p.x+i, p.y-j, dist[p.x][p.y])); list.add( new Cell(p.x-i, p.y-j, dist[p.x][p.y])); list.add( new Cell(p.x+j, p.y+i, dist[p.x][p.y])); list.add( new Cell(p.x-j, p.y+i, dist[p.x][p.y])); list.add( new Cell(p.x+j, p.y-i, dist[p.x][p.y])); list.add( new Cell(p.x-j, p.y-i, dist[p.x][p.y])); } } } for( int i=1; i