import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int[][] mem; static int n; static Queue q; static int[][] sdist; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); mem = new int[n][n]; for(int p = 1; p(); travel(new Pair(new Point(0, 0), 0), a, b); while(!q.isEmpty()){ Pair p = q.poll(); travel(p, a, b); } int dist = sdist[n-1][n-1]; return (dist > 0 ? dist : -1); } static void travel(Pair p, int a, int b){ int x = p.p.x; int y = p.p.y; int d = p.dist; if(x >= n || y >= n || x < 0 || y < 0 || sdist[x][y] != 0) return; sdist[x][y] = d; if(x == n-1 && y == n-1) return; q.addAll(findNeighbours(p, a, b)); } static ArrayList findNeighbours(Pair p, int a, int b){ int x = p.p.x; int y = p.p.y; int d = p.dist; Point[] moves = {new Point(x+a, y+b), new Point(x+a, y-b), new Point(x-a, y+b), new Point(x-a, y-b), new Point(x+b, y+a), new Point(x+b, y-a), new Point(x-b, y+a), new Point(x-b, y-a)}; ArrayList next = new ArrayList<>(moves.length); for(int i = 0; i