1741. Here-There

Do you know the game Here-There? I presume you don't. It's a virtual board game, so you should first learn how this virtual board looks like.

The process of making the board is remarkably simple. You start by taking a square with side of length 3^N, divide it into nine smaller squares of equal size and remove the central one. Then, you repeat the same divide-and-remove-the-centre process with each of the eight smaller squares over and over (N times in total), until you are left with a grid that consists of many little squares with side length 1 – and of many holes. By the way, the number N is called the degree of the board.

The game itself consists of two steps. First, your opponent chooses two squares on the board, one of them will be “Here” and the other one “There”. Your task is to estimate the least number of steps you have to take if you started Here and wanted to get to There. One step consists of moving to another square, which has a common side with the one you're standing on. Obviously, you cannot move over the removed parts of the board. If you guess the number of steps correctly, you get a point.

You would really like to become a master of this game, so you have written down the sizes of the boards and the positions of the Here and There squares from several games in the past. Now, you'd like to find the exact number of steps you need to take to get from Here to There on each of the boards. Each square is described by two numbers between 1 and 3^N, the first of them denoting the column and the second one the row the square is in. The square in the upper left corner of the board has

coordinates (1, 1), as you can see on the picture below.