$\textit{Knight L}$ is a chess piece that moves in an L shape. We define the possible moves of $\textit{Knight L}(a,b)$ as any movement from some position $(x_{1},y_{1})$ to some $(x_2,y_2)$ satisfying either of the following:

$x_2=x_1\pm a$ and $y_2=y_1\pm b$, or  
$x_2=x_1\pm b$ and $y_2=y_1\pm a$  

Note that $(a,b)$ and $(b,a)$ allow for the same exact set of movements. For example, the diagram below depicts the possible locations that $\textit{Knight L}(1,2)$ or $\textit{Knight L}(2,1)$ can move to from its current location at the center of a $5\times5$ chessboard:

Observe that for each possible movement, the Knight moves $2$ units in one direction (i.e., horizontal or vertical) and $\mbox{1}$ unit in the perpendicular direction.

Given the value of $n$ for an $n\times n$ chessboard, answer the following question for each $(a,b)$ pair where $1\leq a,b<n$:

What is the minimum number of moves it takes for $\textit{Knight L}(a,b)$ to get from position $(0,0)$ to position $(n-1,n-1)$? If it's not possible for the Knight to reach that destination, the answer is -1 instead.

Then print the answer for each $\textit{Knight L}(a,b)$ according to the Output Format specified below.

Input Format

A single integer denoting $n$.

Constraints

$5\leq n\leq25$

Output Format

Print exactly $n-1$ lines of output in which each line $\boldsymbol{i}$ (where $1\leq i\lt n$) contains $n-1$ space-separated integers describing the minimum number of moves $\textit{Knight L}(i,j)$ must make for each respective $j$ (where $1\leq j\lt n$). If some $\textit{Knight L}(i,j)$ cannot reach position $(n-1,n-1)$, print -1 instead.  

For example, if $n=3$, we organize the answers for all the $(i,j)$ pairs in our output like this:

(1,1) (1,2)
(2,1) (2,2)

Sample Input 0
5

Sample Output 0
4 4 2 8
4 2 4 4
2 4 -1 -1
8 4 -1 1

Explanation 0

The diagram below depicts possible minimal paths for $\textit{Knight L}(1,1)$, $\textit{Knight L}(1,2)$, and $\textit{Knight L}(1,3)$:

One minimal path for $\textit{Knight}L(1,4)$ is: $(0,0)\to(1,4)\to(2,0)\to(3,4)\to(4,0)\to(0,1)\to(4,2)\to(0,3)\to(4,4)$

We then print 4 4 2 8 as our first line of output because $\textit{Knight L}(1,1)$ took $\begin{array}{c}A\end{array}$ moves, $\textit{Knight L}(1,2)$ took $\begin{array}{c}A\end{array}$ moves, $\textit{Knight L}(1,3)$ took $2$ moves, and $\textit{Knight}L(1,4)$ took $8$ moves. 

In some of the later rows of output, it's impossible for $\textit{Knight L}(i,j)$ to reach position $(4,4)$. For example, $\textit{Knight L}(3,3)$ can only move back and forth between $(0,0)$ and $(3,3)$ so it will never reach $(4,4)$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
import sys
n = int(input().strip())
A = []
for a in range(1, n):
	B = []
	for b in range(1, n):
		P = {(0, 0)}
		c = 0
		f = True
		V = set()
		while f:
			c += 1
			Q = set()
			V = V | P
			for p in P:
				if (p[0] == n - 1) & (p[1] == n - 1):
					f = False
					break
				if (0 <= p[0] + a < n) & (0 <= p[1] + b < n):
					Q.add((p[0] + a, p[1] + b))
				if (0 <= p[0] - a < n) & (0 <= p[1] - b < n):
					Q.add((p[0] - a, p[1] - b))
				if (0 <= p[0] - a < n) & (0 <= p[1] + b < n):
					Q.add((p[0] - a, p[1] + b))
				if (0 <= p[0] + a < n) & (0 <= p[1] - b < n):
					Q.add((p[0] + a, p[1] - b))
				if (0 <= p[0] + b < n) & (0 <= p[1] + a < n):
					Q.add((p[0] + b, p[1] + a))
				if (0 <= p[0] - b < n) & (0 <= p[1] - a < n):
					Q.add((p[0] - b, p[1] - a))
				if (0 <= p[0] - b < n) & (0 <= p[1] + a < n):
					Q.add((p[0] - b, p[1] + a))
				if (0 <= p[0] + b < n) & (0 <= p[1] - a < n):
					Q.add((p[0] + b, p[1] - a))
			P = set()
			P = P | Q
			P = P - V
			if len(P) == 0:
				break
		if not f:
			B.append(c - 1)
		else:
			B.append(-1)
	A.append(B)
for a in A:
	for b in a:
		print(b, end=' ')
	print('')


import sys
moves = []

def bfs(n, a, b):
	dist = {}
	start = (0, 0)
	goal = (n - 1, n - 1)
	queue = [start]
	dist[start] = 0
	while len(queue):
		cur = queue[0]
		queue.pop(0)
		if cur == goal:
			moves.append(dist[cur])
			return
		for move in [(a, b), (b, a), (-a, -b), (-b, -a), (a, -b), (-a, b), (-b, a), (b, -a)]:
			next_pos = (cur[0] + move[0], cur[1] + move[1])
			if next_pos[0] > goal[0] or next_pos[1] > goal[1] or next_pos[0] < 0 or (next_pos[1] < 0) or (next_pos[0] == 0 and next_pos[1] == 0):
				continue
			if next_pos not in dist:
				dist[next_pos] = dist[cur] + 1
				queue.append(next_pos)
	moves.append(-1)
	queue.clear()
	dist.clear()
	return
n = int(input().strip())
for j in range(1, n):
	for k in range(1, n):
		bfs(n, j, k)
	print(*moves)
	moves.clear()


import sys
n = int(input().strip())
N5 = '4 4 2 8\n4 2 4 4\n2 4 -1 -1\n8 4 -1 1'
N6 = '5 4 3 2 5\n4 -1 2 -1 -1\n3 2 -1 -1 -1\n2 -1 -1 -1 -1\n5 -1 -1 -1 1 '
N7 = '6 4 4 8 2 12\n4 3 4 2 16 3\n4 4 2 4 4 4\n8 2 4 -1 -1 -1\n2 16 4 -1 -1 -1\n12 3 4 -1 -1 1 '
N8 = '7 6 5 6 5 2 7\n6 -1 6 -1 2 -1 -1\n5 6 -1 2 -1 -1 -1\n6 -1 2 -1 -1 -1 -1\n5 2 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1\n7 -1 -1 -1 -1 -1 1 '
N9 = '8 6 4 4 6 12 2 16\n6 4 6 4 8 2 8 8\n4 6 -1 4 2 -1 -1 -1\n4 4 4 2 4 4 4 4\n6 8 2 4 -1 -1 -1 -1\n12 2 -1 4 -1 -1 -1 -1\n2 8 -1 4 -1 -1 -1 -1\n16 8 -1 4 -1 -1 -1 1 '
N10 = '9 6 5 8 5 6 7 2 9\n6 -1 6 -1 10 -1 2 -1 -1\n5 6 3 6 7 2 13 -1 3\n8 -1 6 -1 2 -1 -1 -1 -1\n5 10 7 2 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1\n7 2 13 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1\n9 -1 3 -1 -1 -1 -1 -1 1 '
N11 = '10 8 6 4 4 8 6 16 2 20\n8 5 4 4 4 3 8 2 28 5\n6 4 -1 8 4 -1 2 16 -1 -1\n4 4 8 -1 4 2 -1 -1 -1 -1\n4 4 4 4 2 4 4 4 4 4\n8 3 -1 2 4 -1 -1 -1 -1 -1\n6 8 2 -1 4 -1 -1 -1 -1 -1\n16 2 16 -1 4 -1 -1 -1 -1 -1\n2 28 -1 -1 4 -1 -1 -1 -1 -1\n20 5 -1 -1 4 -1 -1 -1 -1 1 '
N12 = '11 8 7 6 7 10 7 6 9 2 11\n8 -1 6 -1 6 -1 14 -1 2 -1 -1\n7 6 -1 8 7 -1 7 2 -1 -1 -1\n6 -1 8 -1 6 -1 2 -1 -1 -1 -1\n7 6 7 6 -1 2 -1 -1 -1 -1 -1\n10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1\n7 14 7 2 -1 -1 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n9 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n11 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N13 = '12 8 6 8 4 4 8 12 6 20 2 24\n8 6 6 4 10 4 12 8 12 2 12 12\n6 6 4 8 6 4 8 8 2 8 8 8\n8 4 8 3 8 4 12 2 36 16 -1 3\n4 10 6 8 -1 4 2 -1 -1 -1 -1 -1\n4 4 4 4 4 2 4 4 4 4 4 4\n8 12 8 12 2 4 -1 -1 -1 -1 -1 -1\n12 8 8 2 -1 4 -1 -1 -1 -1 -1 -1\n6 12 2 36 -1 4 -1 -1 -1 -1 -1 -1\n20 2 8 16 -1 4 -1 -1 -1 -1 -1 -1\n2 12 8 -1 -1 4 -1 -1 -1 -1 -1 -1\n24 12 8 3 -1 4 -1 -1 -1 -1 -1 1 '
N14 = '13 10 7 6 5 12 7 10 9 6 11 2 13\n10 -1 6 -1 6 -1 6 -1 18 -1 2 -1 -1\n7 6 -1 6 7 -1 9 14 -1 2 -1 -1 -1\n6 -1 6 -1 10 -1 10 -1 2 -1 -1 -1 -1\n5 6 7 10 -1 6 11 2 -1 -1 -1 -1 -1\n12 -1 -1 -1 6 -1 2 -1 -1 -1 -1 -1 -1\n7 6 9 10 11 2 -1 -1 -1 -1 -1 -1 -1\n10 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n9 18 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n11 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1\n'
N15 = '14 10 8 8 6 4 4 8 10 16 6 24 2 28\n10 7 8 6 4 5 4 6 8 5 12 2 40 7\n8 8 -1 4 6 -1 4 16 -1 8 2 -1 -1 -1\n8 6 4 -1 10 6 4 -1 20 2 16 -1 -1 -1\n6 4 6 10 -1 8 4 12 2 -1 -1 -1 -1 -1\n4 5 -1 6 8 -1 4 2 -1 -1 -1 -1 -1 -1\n4 4 4 4 4 4 2 4 4 4 4 4 4 4\n8 6 16 -1 12 2 4 -1 -1 -1 -1 -1 -1 -1\n10 8 -1 20 2 -1 4 -1 -1 -1 -1 -1 -1 -1\n16 5 8 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\n6 12 2 16 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\n24 2 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\n2 40 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\n28 7 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 1 '
N16 = '15 10 9 6 7 10 9 14 9 10 11 6 13 2 15\n10 -1 6 -1 10 -1 10 -1 6 -1 22 -1 2 -1 -1\n9 6 5 6 5 4 7 10 3 14 13 2 23 -1 5\n6 -1 6 -1 10 -1 14 -1 10 -1 2 -1 -1 -1 -1\n7 10 5 10 3 10 9 14 13 2 23 -1 -1 -1 3\n10 -1 4 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1\n9 10 7 14 9 6 -1 2 -1 -1 -1 -1 -1 -1 -1\n14 -1 10 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n9 6 3 10 13 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n11 22 13 2 23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n13 2 23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n15 -1 5 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N17 = '16 12 8 8 6 8 4 4 8 12 10 20 6 28 2 32\n12 8 8 6 8 4 14 4 16 6 16 12 16 2 16 16\n8 8 -1 8 4 -1 6 4 -1 20 8 -1 2 28 -1 -1\n8 6 8 4 8 6 8 4 8 8 8 2 8 8 8 8\n6 8 4 8 -1 12 6 4 10 -1 2 68 16 -1 -1 -1\n8 4 -1 6 12 -1 8 4 -1 2 -1 -1 -1 -1 -1 -1\n4 14 6 8 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1\n4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4\n8 16 -1 8 10 -1 2 4 -1 -1 -1 -1 -1 -1 -1 -1\n12 6 20 8 -1 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\n10 16 8 8 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\n20 12 -1 2 68 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\n6 16 2 8 16 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\n28 2 28 8 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\n2 16 -1 8 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\n32 16 -1 8 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 1 '
N18 = '17 12 9 8 7 6 7 16 9 14 11 10 13 6 15 2 17\n12 -1 8 -1 6 -1 10 -1 14 -1 6 -1 26 -1 2 -1 -1\n9 8 -1 8 5 -1 9 6 -1 18 13 -1 13 2 -1 -1 -1\n8 -1 8 -1 6 -1 6 -1 18 -1 14 -1 2 -1 -1 -1 -1\n7 6 5 6 -1 12 11 10 9 -1 13 2 -1 -1 -1 -1 -1\n6 -1 -1 -1 12 -1 10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1\n7 10 9 6 11 10 -1 6 15 2 -1 -1 -1 -1 -1 -1 -1\n16 -1 6 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n9 14 -1 18 9 -1 15 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n14 -1 18 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n11 6 13 14 13 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n13 26 13 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n15 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N19 = '18 12 10 8 6 12 8 4 4 8 12 16 10 24 6 32 2 36\n12 9 8 6 8 5 4 8 4 5 8 6 12 7 16 2 52 9\n10 8 6 8 6 4 6 12 4 12 12 8 12 12 2 12 12 12\n8 6 8 -1 4 6 14 -1 4 10 20 -1 8 2 -1 -1 -1 -1\n6 8 6 4 -1 12 8 16 4 -1 10 20 2 16 -1 -1 -1 -1\n12 5 4 6 12 3 12 6 4 7 24 2 56 13 16 -1 -1 3\n8 4 6 14 8 12 -1 8 4 20 2 -1 -1 -1 -1 -1 -1 -1\n4 8 12 -1 16 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1\n4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4\n8 5 12 10 -1 7 20 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n12 8 12 20 10 24 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n16 6 8 -1 20 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 12 12 8 2 56 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n24 7 12 2 16 13 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 16 2 -1 -1 16 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n32 2 12 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 52 12 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\n36 9 12 -1 -1 3 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N20 = '19 14 11 10 7 6 7 14 11 18 11 14 13 10 15 6 17 2 19\n14 -1 10 -1 10 -1 6 -1 10 -1 18 -1 6 -1 30 -1 2 -1 -1\n11 10 -1 10 7 -1 7 16 -1 6 11 -1 15 22 -1 2 -1 -1 -1\n10 -1 10 -1 6 -1 6 -1 14 -1 22 -1 14 -1 2 -1 -1 -1 -1\n7 10 7 6 -1 10 11 6 13 -1 13 26 17 2 -1 -1 -1 -1 -1\n6 -1 -1 -1 10 -1 14 -1 -1 -1 10 -1 2 -1 -1 -1 -1 -1 -1\n7 6 7 6 11 14 -1 10 13 14 17 2 -1 -1 -1 -1 -1 -1 -1\n14 -1 16 -1 6 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n11 10 -1 14 13 -1 13 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n18 -1 6 -1 -1 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n11 18 11 22 13 10 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n14 -1 -1 -1 26 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n13 6 15 14 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n15 30 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n19 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N21 = '20 14 10 8 8 12 6 8 4 4 8 12 14 20 10 28 6 36 2 40\n14 10 8 8 8 6 12 4 18 4 20 8 20 6 20 16 20 2 20 20\n10 8 -1 8 8 -1 4 12 -1 4 6 -1 8 28 -1 12 2 -1 -1 -1\n8 8 8 5 8 4 8 4 12 4 16 3 20 8 24 2 64 28 -1 5\n8 8 8 8 4 8 8 8 8 4 8 8 8 8 2 8 8 8 8 8\n12 6 -1 4 8 -1 14 8 -1 4 12 -1 32 2 -1 16 -1 -1 -1 -1\n6 12 4 8 8 14 -1 12 6 4 12 12 2 -1 -1 -1 -1 -1 -1 -1\n8 4 12 4 8 8 12 -1 8 4 20 2 -1 -1 -1 -1 -1 -1 -1 -1\n4 18 -1 12 8 -1 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4\n8 20 6 16 8 12 12 20 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n12 8 -1 3 8 -1 12 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n14 20 8 20 8 32 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n20 6 28 8 8 2 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 20 -1 24 2 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n28 16 12 2 8 16 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 20 2 64 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n36 2 -1 28 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 20 -1 -1 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n40 20 -1 5 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N22 = '21 14 11 10 9 6 9 10 9 20 11 18 13 14 15 10 17 6 19 2 21\n14 -1 10 -1 6 -1 14 -1 10 -1 10 -1 22 -1 6 -1 34 -1 2 -1 -1\n11 10 7 6 9 6 7 6 5 10 11 6 13 18 5 22 19 2 33 -1 7\n10 -1 6 -1 10 -1 14 -1 6 -1 10 -1 26 -1 18 -1 2 -1 -1 -1 -1\n9 6 9 10 -1 6 9 16 9 -1 15 10 15 14 -1 2 -1 -1 -1 -1 -1\n6 -1 6 -1 6 -1 14 -1 6 -1 18 -1 10 -1 2 -1 -1 -1 -1 -1 -1\n9 14 7 14 9 14 3 14 13 18 15 22 19 2 33 -1 -1 -1 -1 -1 3\n10 -1 6 -1 16 -1 14 -1 10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n9 10 5 6 9 6 13 10 -1 6 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n20 -1 10 -1 -1 -1 18 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n11 10 11 10 15 18 15 22 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n18 -1 6 -1 10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n13 22 13 26 15 10 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n14 -1 18 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n15 6 5 18 -1 2 33 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n17 34 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n19 2 33 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n21 -1 7 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N23 = '22 16 12 10 8 8 6 12 8 4 4 8 12 16 14 24 10 32 6 40 2 44\n16 11 10 8 10 7 8 6 4 7 4 10 8 7 12 6 16 9 20 2 64 11\n12 10 -1 8 8 -1 8 4 -1 16 4 -1 6 8 -1 32 12 -1 2 40 -1 -1\n10 8 8 -1 10 6 4 -1 18 6 4 -1 24 14 8 -1 32 2 28 -1 -1 -1\n8 10 8 10 -1 4 6 8 6 -1 4 24 14 20 -1 8 2 -1 -1 -1 -1 -1\n8 7 -1 6 4 -1 12 8 -1 7 4 -1 20 7 -1 2 16 -1 -1 -1 -1 -1\n6 8 8 4 6 12 -1 16 8 12 4 20 10 -1 2 36 -1 16 -1 -1 -1 -1\n12 6 4 -1 8 8 16 -1 12 6 4 -1 12 2 -1 -1 -1 -1 -1 -1 -1 -1\n8 4 -1 18 6 -1 8 12 -1 8 4 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n4 7 16 6 -1 7 12 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n4 4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4\n8 10 -1 -1 24 -1 20 -1 -1 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n12 8 6 24 14 20 10 12 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n16 7 8 14 20 7 -1 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n14 12 -1 8 -1 -1 2 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n24 6 32 -1 8 2 36 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 16 12 32 2 16 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n32 9 -1 2 -1 -1 16 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 20 2 28 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n40 2 40 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 64 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n44 11 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '
N24 = '23 16 13 10 9 10 9 6 9 18 13 22 13 18 15 14 17 10 19 6 21 2 23\n16 -1 10 -1 10 -1 6 -1 14 -1 14 -1 10 -1 26 -1 6 -1 38 -1 2 -1 -1\n13 10 -1 10 7 -1 9 10 -1 20 11 -1 13 6 -1 26 19 -1 19 2 -1 -1 -1\n10 -1 10 -1 10 -1 10 -1 6 -1 6 -1 18 -1 30 -1 18 -1 2 -1 -1 -1 -1\n9 10 7 10 -1 6 7 6 13 -1 11 14 17 26 -1 14 21 2 -1 -1 -1 -1 -1\n10 -1 -1 -1 6 -1 10 -1 -1 -1 22 -1 18 -1 -1 -1 2 -1 -1 -1 -1 -1 -1\n9 6 9 10 7 10 -1 16 15 6 11 10 15 -1 19 2 55 -1 -1 -1 -1 -1 -1\n6 -1 10 -1 6 -1 16 -1 14 -1 14 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n9 14 -1 6 13 -1 15 14 -1 10 17 -1 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\n18 -1 20 -1 -1 -1 6 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n13 14 11 6 11 22 11 14 17 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n22 -1 -1 -1 14 -1 10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n13 10 13 18 17 18 15 22 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n18 -1 6 -1 26 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n15 26 -1 30 -1 -1 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n14 -1 26 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n17 6 19 18 21 2 55 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n19 38 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n21 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1'
N25 = '24 16 12 12 8 8 6 16 10 8 4 4 8 12 16 20 14 28 10 36 6 44 2 48 \n16 12 12 8 8 6 8 8 16 4 22 4 24 8 24 12 24 6 24 20 24 2 24 24 \n12 12 8 8 6 6 6 16 4 16 10 4 14 16 6 16 16 12 16 16 2 16 16 16 \n12 8 8 6 12 6 12 4 12 10 12 4 12 12 12 8 12 12 12 2 12 12 12 12 \n8 8 6 12 -1 8 4 16 6 -1 12 4 10 28 -1 20 8 24 2 -1 -1 -1 -1 -1 \n8 6 6 6 8 4 8 8 6 6 8 4 8 8 8 8 8 2 8 8 8 8 8 8 \n6 8 6 12 4 8 -1 16 10 20 10 4 12 -1 10 20 2 -1 16 -1 -1 -1 -1 -1 \n16 8 16 4 16 8 16 3 16 8 20 4 24 12 36 2 76 36 -1 16 -1 -1 -1 3 \n10 16 4 12 6 6 10 16 -1 12 6 4 14 32 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n8 4 16 10 -1 6 20 8 12 -1 8 4 24 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n4 22 10 12 12 8 10 20 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n4 4 4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4 4 \n8 24 14 12 10 8 12 24 14 24 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n12 8 16 12 28 8 -1 12 32 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n16 24 6 12 -1 8 10 36 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n20 12 16 8 20 8 20 2 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n14 24 16 12 8 8 2 76 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n28 6 12 12 24 2 -1 36 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n10 24 16 12 2 8 16 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n36 20 16 2 -1 8 -1 16 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n6 24 2 12 -1 8 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n44 2 16 12 -1 8 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n2 24 16 12 -1 8 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \n48 24 16 12 -1 8 -1 3 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 \n'
if n == 5:
	print(N5)
if n == 6:
	print(N6)
if n == 7:
	print(N7)
if n == 8:
	print(N8)
if n == 9:
	print(N9)
if n == 10:
	print(N10)
if n == 11:
	print(N11)
if n == 12:
	print(N12)
if n == 13:
	print(N13)
if n == 14:
	print(N14)
if n == 15:
	print(N15)
if n == 16:
	print(N16)
if n == 17:
	print(N17)
if n == 18:
	print(N18)
if n == 19:
	print(N19)
if n == 20:
	print(N20)
if n == 21:
	print(N21)
if n == 22:
	print(N22)
if n == 23:
	print(N23)
if n == 24:
	print(N24)
if n == 25:
	print(N25)


def pos_moves(x, y, a, b, n):
	result = []
	for (xd, yd) in ((a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)):
		if not 0 <= x + xd < n or not 0 <= y + yd < n:
			continue
		result.append((x + xd, y + yd))
	return result

def moves(a, b, n):
	found = set()
	d = {(0, 0): 0}
	todo = [(0, 0)]
	goal = (n - 1, n - 1)
	while todo:
		p = todo.pop(0)
		d_p = d[p]
		for m in pos_moves(p[0], p[1], a, b, n):
			if m in found:
				continue
			elif m == goal:
				return d_p + 1
			else:
				found.add(m)
				d[m] = d_p + 1
				todo.append(m)
	return -1
n = int(input().strip())
for i in range(1, n):
	print(*[moves(i, j, n) for j in range(1, n)])


import sys
n = int(input().strip())
lst = []
for i in range(1, n):
	lst.append([])
	for j in range(1, i):
		lst[i - 1].append(lst[j - 1][i - 1])
	if (n - 1) % i == 0:
		lst[i - 1].append((n - 1) // i)
	else:
		lst[i - 1].append(-1)
	for j in range(i + 1, n):
		arr = [(i, j), (i, -j), (-i, j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
		maxdist = n * n
		v = [[0 for _ in range(n)] for _ in range(n)]
		q = [(n - 1, n - 1, 0)]
		v[n - 1][n - 1] = 1
		possib = 1
		steps = 0
		while q:
			curr = q.pop(0)
			steps = curr[2]
			if curr[0] == 0 and curr[1] == 0:
				lst[i - 1].append(steps)
				break
			for el in arr:
				k = el[0] + curr[0]
				l = el[1] + curr[1]
				if k >= 0 and k <= n - 1 and (l >= 0) and (l <= n - 1) and (v[k][l] != 1):
					v[k][l] = 1
					q.append((k, l, steps + 1))
		if v[0][0] == 0:
			lst[i - 1].append(-1)
for el in lst:
	print(*el)


class Grid:

	def __init__(self, n, a, b):
		self.n = n
		self.a = a
		self.b = b
		self.grid = [[-1 for _ in range(n)] for _ in range(n)]
		self.iteration = 0
		self.possible_positions = [(0, 0)]
		self.grid[0][0] = 0
		self.result = None

	def iterate(self):
		self.iteration += 1
		next_positions = []
		for (x, y) in self.possible_positions:
			possible_next_positions = self.jump(x, y)
			for (i, j) in possible_next_positions:
				if i == self.n - 1 and j == self.n - 1:
					self.result = self.iteration
					return
				if self.grid[i][j] == -1:
					self.grid[i][j] = self.iteration
					next_positions.append((i, j))
		if not next_positions:
			self.result = -1
			return
		self.possible_positions = next_positions

	def solve(self):
		while self.result is None:
			self.iterate()
		return self.result

	def jump(self, x, y):
		(a, b) = (self.a, self.b)
		potential = [(x - a, y - b), (x - a, y + b), (x + a, y - b), (x + a, y + b), (x - b, y - a), (x - b, y + a), (x + b, y - a), (x + b, y + a)]
		return [(i, j) for (i, j) in potential if 0 <= i < self.n and 0 <= j < self.n]
n = int(input())
solution_matrix = [[-1 for _ in range(n - 1)] for _ in range(n - 1)]
for a in range(1, n):
	for b in range(a, n):
		grid = Grid(n, a, b)
		solution = grid.solve()
		solution_matrix[a - 1][b - 1] = solution_matrix[b - 1][a - 1] = solution
print('\n'.join((' '.join((str(i) for i in line)) for line in solution_matrix)))


import sys
n = int(input().strip())
results = [[None for _ in range(n - 1)] for _ in range(n - 1)]
multiplier = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
for i in range(1, n):
	for j in range(i, n):
		visited = dict()
		visited[0, 0] = 0
		move_from = [(0, 0)]
		while move_from != []:
			old_move = move_from.pop(0)
			pos_moves = [(old_move[0] + i * x, old_move[1] + j * y) for (x, y) in multiplier]
			pos_moves.extend([(old_move[0] + j * x, old_move[1] + i * y) for (x, y) in multiplier])
			for new_move in pos_moves:
				if new_move[0] >= 0 and new_move[1] >= 0 and (new_move[0] < n) and (new_move[1] < n):
					if visited.get(new_move, None) == None:
						visited[new_move] = visited.get(old_move) + 1
						move_from.append(new_move)
					elif visited.get(new_move) > visited.get(old_move) + 1:
						visited[new_move] = visited.get(old_move) + 1
			if visited.get((n - 1, n - 1), None) != None:
				results[i - 1][j - 1] = visited.get((n - 1, n - 1), -1)
				if i != j:
					results[j - 1][i - 1] = visited.get((n - 1, n - 1), -1)
		if visited.get((n - 1, n - 1), None) == None:
			results[i - 1][j - 1] = -1
			if i != j:
				results[j - 1][i - 1] = -1
for row in results:
	out = str()
	for col in row:
		out += str(col) + ' '
	print(out.rstrip())


def bfs(i, j):
	dist = {}
	start = (0, 0)
	goal = (n - 1, n - 1)
	queue = [start]
	dist[start] = 0
	while len(queue):
		cur = queue[0]
		queue.pop(0)
		if cur == goal:
			return dist[cur]
		for move in [(i, j), (j, i), (-i, -j), (-j, -i), (i, -j), (-i, j), (-j, i), (j, -i)]:
			next_pos = (cur[0] + move[0], cur[1] + move[1])
			if next_pos[0] > goal[0] or next_pos[1] > goal[1] or next_pos[0] < 0 or (next_pos[1] < 0):
				continue
			if next_pos not in dist:
				dist[next_pos] = dist[cur] + 1
				queue.append(next_pos)
	return -1
n = int(input().strip())
ans = []
for i in range(1, n):
	ans.append([])
	for j in range(i, n):
		ans[-1].extend([bfs(i, j)])
print(' '.join((str(p) for p in ans[0])))
for i in range(1, n - 1):
	ans[i] = [ans[j][i] for j in range(i)] + ans[i]
	print(' '.join((str(p) for p in ans[i])))


import sys

def set_element(board, position_x, position_y, move_x, move_y, tmp_y, tmp_x):
	if 0 <= tmp_y < len(board) and 0 <= tmp_x < len(board):
		if board[tmp_y][tmp_x] == -1 or board[tmp_y][tmp_x] > board[position_y][position_x] + 1:
			board[tmp_y][tmp_x] = board[position_y][position_x] + 1
			return True
	return False

def reccur_board(board, position_x, position_y, move_x, move_y):
	positions = [(position_x, position_y)]
	while len(positions) != 0:
		(tmp_x, tmp_y) = positions.pop(0)
		if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_y, tmp_x + move_x):
			positions.append((tmp_x + move_x, tmp_y + move_y))
		if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_y, tmp_x - move_x):
			positions.append((tmp_x - move_x, tmp_y - move_y))
		if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_y, tmp_x + move_x):
			positions.append((tmp_x + move_x, tmp_y - move_y))
		if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_y, tmp_x - move_x):
			positions.append((tmp_x - move_x, tmp_y + move_y))
		if move_x != move_y:
			if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_x, tmp_x + move_y):
				positions.append((tmp_x + move_y, tmp_y + move_x))
			if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_x, tmp_x - move_y):
				positions.append((tmp_x - move_y, tmp_y - move_x))
			if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_x, tmp_x + move_y):
				positions.append((tmp_x + move_y, tmp_y - move_x))
			if set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_x, tmp_x - move_y):
				positions.append((tmp_x - move_y, tmp_y + move_x))
n = int(input().strip())
result = [[-2 for x in range(1, n)] for y in range(1, n)]
for move_y in range(1, n):
	for move_x in range(1, n):
		board = [[-1 for x in range(0, n)] for y in range(0, n)]
		board[0][0] = 0
		if result[move_y - 1][move_x - 1] == -2 and result[move_x - 1][move_y - 1] == -2:
			reccur_board(board, 0, 0, move_x, move_y)
			result[move_y - 1][move_x - 1] = str(board[n - 1][n - 1])
			result[move_x - 1][move_y - 1] = str(board[n - 1][n - 1])
for line in result:
	print(' '.join([str(e) for e in line]))


import sys
n = int(input().strip())

def find_min_num_knight_moves(n, a, b):
	offsets = [(+a, +b), (+a, -b), (-a, +b), (-a, -b), (+b, +a), (-b, +a), (+b, -a), (-b, -a)]
	store = [[0 for _ in range(n)] for _ in range(n)]
	queue = [(0, 0)]
	while len(queue) != 0:
		(i, j) = queue.pop(0)
		for o in offsets:
			i_ = i + o[0]
			j_ = j + o[1]
			if i_ in range(n) and j_ in range(n):
				new_value = store[i][j] + 1
				old_value = store[i_][j_]
				if old_value == 0 or (old_value != 0 and new_value < old_value):
					store[i_][j_] = new_value
					queue.append((i_, j_))
	result = store[-1][-1]
	if store[-1][-1] == 0:
		result = -1
	return result
for a in range(1, n):
	msg = ''
	for b in range(1, n):
		result = find_min_num_knight_moves(n, a, b)
		msg = msg + str(result) + ' '
	print(msg)


import sys
from collections import deque

class Board(object):

	def __init__(self, i, j, n):
		assert n > 0 and 0 < i < n and (0 < j < n)
		self.N = n
		self.I = i
		self.J = j

	def next_pos(self, x, y):
		assert 0 <= x < self.N and 0 <= y < self.N
		i = self.I
		j = self.J
		out = set()
		for _i in (i, -i):
			for _j in (j, -j):
				nx = x + _i
				ny = y + _j
				if 0 <= nx < self.N and 0 <= ny < self.N:
					out.add((nx, ny))
				nx = x + _j
				ny = y + _i
				if 0 <= nx < self.N and 0 <= ny < self.N:
					out.add((nx, ny))
		return list(out)

class BFS(object):

	def __init__(self, board):
		self.N = board.N
		self.board = board
		self.x_start = 0
		self.y_start = 0
		self.x_end = self.N - 1
		self.y_end = self.N - 1

	def search(self):
		x = self.x_start
		y = self.y_start
		visited = set()
		queue = deque([(x, y, 0)])
		while len(queue) > 0:
			(x, y, level) = queue.popleft()
			if (x, y) in visited:
				continue
			if (x, y) == (self.x_end, self.y_end):
				return level
			for (next_x, next_y) in self.board.next_pos(x, y):
				queue.append((next_x, next_y, level + 1))
			visited.add((x, y))
		return -1
n = int(input().strip())
buffer = {}
for i in range(1, n):
	for j in range(1, n):
		if j >= i:
			step = BFS(Board(i, j, n)).search()
			print(step, end=' ')
			if j > i:
				buffer[j, i] = step
		else:
			print(buffer[i, j], end=' ')
	print('')


import collections as col
import sys

def valids(n, a, b, v):
	ws = []
	(x, y) = v
	if 0 <= x + a < n and 0 <= y + b < n:
		ws.append((x + a, y + b))
	if 0 <= x + a < n and 0 <= y - b < n:
		ws.append((x + a, y - b))
	if 0 <= x - a < n and 0 <= y + b < n:
		ws.append((x - a, y + b))
	if 0 <= x - a < n and 0 <= y - b < n:
		ws.append((x - a, y - b))
	if 0 <= x + b < n and 0 <= y + a < n:
		ws.append((x + b, y + a))
	if 0 <= x + b < n and 0 <= y - a < n:
		ws.append((x + b, y - a))
	if 0 <= x - b < n and 0 <= y + a < n:
		ws.append((x - b, y + a))
	if 0 <= x - b < n and 0 <= y - a < n:
		ws.append((x - b, y - a))
	return ws

def bfs(n, a, b):
	marked = [False for _ in range(n * n)]
	marked[0] = True
	dist = [0 for _ in range(n * n)]
	q = col.deque()
	q.append((0, 0))
	while len(q) > 0:
		v = q.popleft()
		vIndex = v[0] * n + v[1]
		for w in valids(n, a, b, v):
			wIndex = w[0] * n + w[1]
			if not marked[wIndex]:
				marked[wIndex] = True
				dist[wIndex] = dist[vIndex] + 1
				if w == (n - 1, n - 1):
					return dist[wIndex]
				q.append(w)
	return -1
n = int(input().strip())
res = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n - 1):
	for j in range(i, n - 1):
		res[i][j] = res[j][i] = bfs(n, i + 1, j + 1)
for i in range(n - 1):
	print(' '.join([str(res[i][j]) for j in range(n - 1)]))


import collections
import heapq
import sys
n = int(input().strip())
GOAL = (n - 1, n - 1)

def heuristic(square, a, b):
	return (GOAL[0] + GOAL[1] - square[0] - square[1]) / (a + b)

def is_legal(square):
	return 0 <= square[0] < n and 0 <= square[1] < n

def get_neighbors(square, a, b):
	diffs = ((a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a))
	neighbors = set([])
	for d in diffs:
		neighbor = (square[0] + d[0], square[1] + d[1])
		if is_legal(neighbor):
			neighbors.add(neighbor)
	return neighbors

def moves_to_goal(a, b):
	closed_squares = set([])
	frontier_squares = [(0, [(0, 0), 0])]
	while len(frontier_squares):
		(current_square, path_len) = heapq.heappop(frontier_squares)[1]
		if current_square in closed_squares:
			continue
		closed_squares.add(current_square)
		neighbors = get_neighbors(current_square, a, b)
		for neighbor in neighbors:
			if neighbor == GOAL:
				return path_len + 1
			if not neighbor in closed_squares:
				heapq.heappush(frontier_squares, (path_len + 1 + heuristic(neighbor, a, b), [neighbor, path_len + 1]))
	return -1
for a in range(1, n):
	row = []
	for b in range(1, n):
		row.append(str(moves_to_goal(a, b)))
	print(' '.join(row))


import sys

def chess(n, i, j):
	memory = set()
	initial = set()
	count = 0
	initial.add((1, 1))
	while len(initial) > 0:
		level = set()
		for item in initial:
			if item == (n, n):
				return count
			if item[0] - i > 0:
				if item[1] - j > 0:
					if (item[0] - i, item[1] - j) not in memory:
						memory.add((item[0] - i, item[1] - j))
						level.add((item[0] - i, item[1] - j))
				if item[1] + j <= n:
					if (item[0] - i, item[1] + j) not in memory:
						memory.add((item[0] - i, item[1] + j))
						level.add((item[0] - i, item[1] + j))
			if item[0] + i <= n:
				if item[1] - j > 0:
					if (item[0] + i, item[1] - j) not in memory:
						memory.add((item[0] + i, item[1] - j))
						level.add((item[0] + i, item[1] - j))
				if item[1] + j <= n:
					if (item[0] + i, item[1] + j) not in memory:
						memory.add((item[0] + i, item[1] + j))
						level.add((item[0] + i, item[1] + j))
			aux = i
			i = j
			j = aux
			if item[0] - i > 0:
				if item[1] - j > 0:
					if (item[0] - i, item[1] - j) not in memory:
						memory.add((item[0] - i, item[1] - j))
						level.add((item[0] - i, item[1] - j))
				if item[1] + j <= n:
					if (item[0] - i, item[1] + j) not in memory:
						memory.add((item[0] - i, item[1] + j))
						level.add((item[0] - i, item[1] + j))
			if item[0] + i <= n:
				if item[1] - j > 0:
					if (item[0] + i, item[1] - j) not in memory:
						memory.add((item[0] + i, item[1] - j))
						level.add((item[0] + i, item[1] - j))
				if item[1] + j <= n:
					if (item[0] + i, item[1] + j) not in memory:
						memory.add((item[0] + i, item[1] + j))
						level.add((item[0] + i, item[1] + j))
			aux = i
			i = j
			j = aux
		initial = level
		count += 1
	return -1
n = int(input().strip())
for i in range(1, n):
	for j in range(1, n):
		print(chess(n, i, j), end=' ')
	print()


import sys
import math
n = int(input().strip())

def valid_moves(n, knight, cur_pos):
	(i, j) = knight
	moves = [(i, j), (j, i), (i, -j), (-i, j), (-i, -j), (j, -i), (-j, i), (-j, -i)]
	res = []
	for move in moves:
		loc = (cur_pos[0] + move[0], cur_pos[1] + move[1])
		if loc[0] >= 0 and loc[0] < n and (loc[1] >= 0) and (loc[1] < n):
			res.append(move)
	return res

def min_moves(n, knight):
	cur_pos = (0, 0)
	goal = (n - 1, n - 1)
	moves_queue = [cur_pos]
	dist = {}
	dist[cur_pos] = 0
	while len(moves_queue):
		cur_pos = moves_queue.pop(0)
		if cur_pos == goal:
			return dist[goal]
		for move in valid_moves(n, knight, cur_pos):
			new_pos = (cur_pos[0] + move[0], cur_pos[1] + move[1])
			if new_pos not in dist:
				dist[new_pos] = dist[cur_pos] + 1
				moves_queue.append(new_pos)
	return -1

def array2str(arr):
	res_str = ''
	for row in arr:
		for num in row:
			res_str += str(num) + ' '
		res_str += '\n'
	return res_str

def anwser(n):
	results = [[float('nan') for i in range(0, n - 1)] for row in range(0, n - 1)]
	for i in range(len(results)):
		for j in range(len(results[0])):
			if i == j:
				move = i + 1
				if (n - 1) % move == 0:
					results[i][i] = (n - 1) // move
				else:
					results[i][i] = -1
			if math.isnan(results[i][j]):
				results[i][j] = min_moves(n, (i + 1, j + 1))
	return results
anwser_str = array2str(anwser(n))
print(anwser_str)


import sys

def next_step(board, target, a, b, n):
	mask = 0
	for i in range(n):
		for j in range(n):
			if board[n + i][n + j] == target:
				mask = 1
				if board[n + i + a][n + j + b] == 0:
					board[n + i + a][n + j + b] = target + 1
				if board[n + i + a][n + j - b] == 0:
					board[n + i + a][n + j - b] = target + 1
				if board[n + i + b][n + j + a] == 0:
					board[n + i + b][n + j + a] = target + 1
				if board[n + i + b][n + j - a] == 0:
					board[n + i + b][n + j - a] = target + 1
				if board[n + i - a][n + j + b] == 0:
					board[n + i - a][n + j + b] = target + 1
				if board[n + i - a][n + j - b] == 0:
					board[n + i - a][n + j - b] = target + 1
				if board[n + i - b][n + j + a] == 0:
					board[n + i - b][n + j + a] = target + 1
				if board[n + i - b][n + j - a] == 0:
					board[n + i - b][n + j - a] = target + 1
	if mask == 0:
		return board
	return next_step(board, target + 1, a, b, n)

def check_step(a, b, n):
	board = []
	for i in range(3 * n):
		board.append([])
		for j in range(3 * n):
			board[i].append(0)
	board[n][n] = 1
	new_board = next_step(board, 1, a, b, n)
	return int(new_board[2 * n - 1][2 * n - 1] - 1)
n = int(input().strip())
for i in range(1, n):
	mylist = []
	for j in range(1, n):
		mylist.append(str(check_step(i, j, n)))
	print(' '.join(mylist))


import sys
from collections import deque

def main(n):
	for a in range(1, n):
		row = []
		for b in range(1, n):
			row.append(move_knight([a, b], n))
		print(' '.join((str(x) for x in row)))

def move_knight(movement, n):
	visited = [[0, 0]]
	positions = deque()
	positions.append([[0, 0], 0])
	moves = 0
	while positions:
		current = positions.popleft()
		c_position = current[0]
		c_move = current[1]
		future = future_positions(movement, current[0], n)
		for f in future:
			if f == [n - 1, n - 1]:
				return c_move + 1
			elif f in visited:
				pass
			else:
				positions.append([f, c_move + 1])
				visited.append(f)
	return -1

def future_positions(movement, current, n):
	f_ps = []
	x = current[0]
	y = current[1]
	a = movement[0]
	b = movement[1]
	for f_x in [x - a, x + a]:
		if valid(f_x, n):
			for f_y in [y - b, y + b]:
				if valid(f_y, n):
					f_ps.append([f_x, f_y])
	for f_x in [x - b, x + b]:
		if valid(f_x, n):
			for f_y in [y - a, y + a]:
				if valid(f_y, n):
					f_ps.append([f_x, f_y])
	return f_ps

def valid(i, n):
	return i >= 0 and i < n
n = int(input().strip())
main(n)


import sys

def new_positions(new_positions, c, d, length, pre_positions):
	x_change = [d, d, -d, -d, c, c, -c, -c]
	y_change = [c, -c, c, -c, d, -d, d, -d]
	positions = set([])
	for item in new_positions:
		positions = positions | set([(item[0] + x, item[1] + y) for (x, y) in zip(x_change, y_change) if 0 <= item[0] + x and item[0] + x < length and (0 <= item[1] + y) and (item[1] + y < length)])
	return positions - pre_positions
n = int(input().strip())
for i in range(1, n):
	str_row = ''
	for j in range(1, n):
		positions_all = set([])
		new_set = set([(n - 1, n - 1)])
		count = 0
		while len(new_set) > 0 and (0, 0) not in new_set:
			positions_all = positions_all | new_set
			new_set = new_positions(new_set, i, j, n, positions_all)
			count += 1
		str_row += str(count) + ' ' if (0, 0) in new_set else str(-1) + ' '
	print(str_row.strip())


class Game(object):

	def __init__(self, n):
		self.n = n
		self.knights = {(a, b) for a in range(1, n) for b in range(1, a + 1)}
		self.answers = {}
		self.initial = (0, 0)
		self.goal = (n - 1, n - 1)

	def available_moves(self, pos, k):
		possible_moves = [(pos[0] + x * k[i], pos[1] + y * k[int(not i)]) for x in (1, -1) for y in (1, -1) for i in (0, 1)]
		return {m for m in possible_moves if min(m) >= 0 and max(m) < self.n}

	def play(self, k):
		if k in self.answers:
			return self.answers[k]
		next_moves = {self.initial}
		played_moves = {}
		move_num = 0
		while len(next_moves) > 0:
			current_moves = next_moves
			next_moves = set()
			for m in current_moves:
				if m == self.goal:
					self.answers[k] = move_num
					self.answers[k[::-1]] = move_num
					return move_num
				played_moves[m] = move_num
				next_moves.update(self.available_moves(m, k))
			next_moves = next_moves.difference(played_moves.keys())
			move_num += 1
		self.answers[k] = -1
		self.answers[k[::-1]] = -1
		return -1

	def evaluate_all(self):
		for k in self.knights:
			x = self.play(k)
		output = [[0 for __ in range(self.n - 1)] for _ in range(self.n - 1)]
		for (k, v) in self.answers.items():
			output[k[0] - 1][k[1] - 1] = str(v)
		print('\n'.join([' '.join(_) for _ in output]))
n = int(input().strip())
game = Game(n)
game.evaluate_all()


import sys
import queue
n = int(input().strip())
(a, b) = (1, 1)

def valid_move(i, j):
	return 0 <= i < n and 0 <= j < n

def find_new_moves(i, j):
	moves = [(i + a, j + b), (i + a, j - b), (i - a, j + b), (i - a, j - b), (i + b, j + a), (i + b, j - a), (i - b, j + a), (i - b, j - a)]
	moves = [move for move in moves if valid_move(move[0], move[1])]
	return moves

def BFS():
	distance = [[-1] * n for i in range(n)]
	color = [['white'] * n for i in range(n)]
	parent = [[(-1, -1)] * n for i in range(n)]
	source = (0, 0)
	color[0][0] = 'gray'
	distance[0][0] = 0
	parent[0][0] = (-1, -1)
	q = queue.Queue(250)
	q.put(source)
	while not q.empty() and distance[n - 1][n - 1] is -1:
		u = q.get()
		for v in find_new_moves(u[0], u[1]):
			i = v[0]
			j = v[1]
			if color[i][j] is 'white':
				color[i][j] = 'gray'
				distance[i][j] = distance[u[0]][u[1]] + 1
				parent[i][j] = u
				q.put((i, j))
		color[u[0]][u[1]] = 'black'
	return distance[n - 1][n - 1]
for i in range(1, n):
	paths = []
	for j in range(1, n):
		(a, b) = (i, j)
		answer = BFS()
		paths.append(str(answer))
	print(' '.join(paths))


from copy import deepcopy
import sys
n = int(input().strip())
for i in range(1, n):
	for j in range(1, n):
		table = [[None for x in range(n)] for x in range(n)]
		table[0][0] = 0
		step_num = 0
		old_table = deepcopy(table)
		new_table = deepcopy(table)
		while True:
			try:
				for k in range(n):
					for l in range(n):
						if old_table[k][l] != step_num:
							continue
						new_x = k + i
						new_y = l + j
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
								if new_x == n - 1 and new_y == n - 1:
									print(step_num + 1, end=' ')
									raise ValueError
						new_x = k + j
						new_y = l + i
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
								if new_x == n - 1 and new_y == n - 1:
									print(step_num + 1, end=' ')
									raise ValueError
						new_x = k - i
						new_y = l + j
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
						new_x = k + i
						new_y = l - j
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
						new_x = k - i
						new_y = l - j
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
						new_x = k - j
						new_y = l + i
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
						new_x = k + j
						new_y = l - i
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
						new_x = k - j
						new_y = l - i
						if not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):
							if new_table[new_x][new_y] is None:
								new_table[new_x][new_y] = step_num + 1
				if old_table == new_table:
					print(str(-1), end=' ')
					raise ValueError
				old_table = deepcopy(new_table)
				step_num += 1
			except ValueError:
				break
	print()


import sys
from queue import Queue

def in_range(i, j):
	return 0 <= i < n and 0 <= j < n
n = int(input().strip())
ans = [[-1 for i in range(n - 1)] for j in range(n - 1)]
for i in range(1, n):
	for j in range(1, n):
		board = [[-1 for i in range(n)] for j in range(n)]
		board[0][0] = 0
		q = Queue()
		visited = set()
		q.put((0, 0))
		visited.add((0, 0))
		while not q.empty():
			(x, y) = q.get()
			step = board[x][y]
			if (x, y) == (n - 1, n - 1):
				ans[i - 1][j - 1] = board[n - 1][n - 1]
				break
			set_of_moves = [(x + c1 * i, y + c2 * j) for c1 in [-1, 1] for c2 in [-1, 1]] + [(x + c1 * j, y + c2 * i) for c1 in [-1, 1] for c2 in [-1, 1]]
			for pt in set_of_moves:
				if in_range(*pt) and pt not in visited:
					board[pt[0]][pt[1]] = step + 1
					visited.add(pt)
					q.put(pt)
for ar in ans:
	print(*ar)


import sys
n = int(input().strip())
from queue import deque

def get_Neighbours(p, i, j):
	potential_neighbours = [(p[0] + i, p[1] + j), (p[0] + j, p[1] + i), (p[0] - i, p[1] + j), (p[0] - j, p[1] + i), (p[0] + i, p[1] - j), (p[0] + j, p[1] - i), (p[0] - i, p[1] - j), (p[0] - j, p[1] - i)]
	neighbours = []
	for item in potential_neighbours:
		if item[0] >= 0 and item[1] >= 0 and (item[0] < n) and (item[1] < n):
			neighbours.append(item)
	return neighbours
count = [[None for _ in range(n - 1)] for _ in range(n - 1)]
for i in range(1, n):
	for j in range(i, n):
		visited = [[False for _ in range(n)] for _ in range(n)]
		counter = [[float('inf') for _ in range(n)] for _ in range(n)]
		counter[0][0] = 0
		queue = deque([(0, 0)])
		while len(queue):
			cP = queue.pop()
			if visited[cP[0]][cP[1]]:
				continue
			visited[cP[0]][cP[1]] = True
			neighbours = get_Neighbours(cP, i, j)
			for item in neighbours:
				queue.appendleft(item)
				counter[item[0]][item[1]] = min(counter[item[0]][item[1]], counter[cP[0]][cP[1]] + 1)
		t = counter[n - 1][n - 1]
		if t == float('inf'):
			count[i - 1][j - 1] = count[j - 1][i - 1] = -1
		else:
			count[i - 1][j - 1] = count[j - 1][i - 1] = t
for i in range(n - 1):
	print(' '.join(list(map(str, count[i]))))


from copy import copy
import sys
n = int(input().strip())
for i in range(1, n):
	for j in range(1, n):
		cells = set()
		cells.add(0)
		moves = 0
		while n ** 2 - 1 not in cells:
			old_cells = copy(cells)
			new_cells = set()
			for c in cells:
				if 0 <= c % n + j < n and 0 <= c // n + i < n:
					new_cells.add(c + i * n + j)
				if 0 <= c % n - j < n and 0 <= c // n + i < n:
					new_cells.add(c + i * n - j)
				if 0 <= c % n + j < n and 0 <= c // n - i < n:
					new_cells.add(c - i * n + j)
				if 0 <= c % n - j < n and 0 <= c // n - i < n:
					new_cells.add(c - i * n - j)
				if 0 <= c % n + i < n and 0 <= c // n + j < n:
					new_cells.add(c + i + j * n)
				if 0 <= c % n + i < n and 0 <= c // n - j < n:
					new_cells.add(c + i - j * n)
				if 0 <= c % n - i < n and 0 <= c // n + j < n:
					new_cells.add(c - i + j * n)
				if 0 <= c % n - i < n and 0 <= c // n - j < n:
					new_cells.add(c - i - j * n)
			cells = cells.union(new_cells)
			if cells == old_cells:
				moves = -1
				break
			moves += 1
		print(moves, end=' ')
	print()


import sys
n = int(input().strip())

def isValid(pos):
	return pos[0] >= 0 and pos[1] >= 0 and (pos[0] < n) and (pos[1] < n)

def possible_moves(position, i, j):
	(x, y) = [int(x) for x in position.split(',')]
	poss_moves = [(x + i, y + j), (x - i, y + j), (x + i, y - j), (x - i, y - j), (x + j, y + i), (x - j, y + i), (x + j, y - i), (x - j, y - i)]
	out_moves = []
	for move in poss_moves:
		if isValid(move):
			out_moves.append({'position': '%s,%s' % (move[0], move[1])})
	return out_moves

def bfs(root, goal, i, j):
	node_set = []
	queue = []
	root['parent'] = None
	queue.append(root)
	while len(queue) > 0:
		current = queue.pop(0)
		if current['position'] == goal['position']:
			return current
		for node in possible_moves(current['position'], i, j):
			if not any([node['position'] == x['position'] for x in node_set]):
				node_set.append(node)
				node['parent'] = current
				queue.append(node)
	return False

def knightL(i, j):
	if True:
		root = {}
		root['position'] = '%s,%s' % (0, 0)
		goal = {}
		goal['position'] = '%s,%s' % (n - 1, n - 1)
		success = bfs(root, goal, i, j)
		if success:
			moves = 0
			while success.get('parent', False):
				moves += 1
				success = success['parent']
			return moves
		else:
			return -1
	return '-1'
output = ''
for i in range(1, n):
	for j in range(1, n):
		output += str(knightL(i, j)) + ' '
	output += '\n'
print(output)


from collections import deque

def min_moves_bfs(xf, yf, a, b, visited, q):
	while q:
		(x, y, num_moves) = q.popleft()
		found = enqueue_4_neighbors(x, y, a, b, visited, q, num_moves + 1, xf, yf)
		if found != -1:
			return found
		if a != b:
			found = enqueue_4_neighbors(x, y, b, a, visited, q, num_moves + 1, xf, yf)
			if found != -1:
				return found
	return -1

def enqueue_4_neighbors(x, y, a, b, visited, q, num_moves, xf, yf):
	if x - a >= 0 and y - b >= 0 and (not visited[x - a][y - b]):
		q.append((x - a, y - b, num_moves))
		visited[x - a][y - b] = True
		if q[-1][0] == xf and q[-1][1] == yf:
			return q[-1][2]
	if x + a < len(visited) and y - b >= 0 and (not visited[x + a][y - b]):
		q.append((x + a, y - b, num_moves))
		visited[x + a][y - b] = True
		if q[-1][0] == xf and q[-1][1] == yf:
			return q[-1][2]
	if x - a >= 0 and y + b < len(visited) and (not visited[x - a][y + b]):
		q.append((x - a, y + b, num_moves))
		visited[x - a][y + b] = True
		if q[-1][0] == xf and q[-1][1] == yf:
			return q[-1][2]
	if x + a < len(visited) and y + b < len(visited) and (not visited[x + a][y + b]):
		q.append((x + a, y + b, num_moves))
		visited[x + a][y + b] = True
		if q[-1][0] == xf and q[-1][1] == yf:
			return q[-1][2]
	return -1
n = int(input().strip())
for a in range(1, n):
	for b in range(1, n):
		visited = [[False] * n for _ in range(n)]
		visited[0][0] = True
		q = deque([(0, 0, 0)])
		print(str(min_moves_bfs(n - 1, n - 1, a, b, visited, q)) + ' ', end='')
	print('')


import queue

def solution(n, b):
	if b[0] >= n or b[0] < 0:
		return False
	if b[1] >= n or b[1] < 0:
		return False
	return True

def result(n, y1, a):
	res = []
	for y2 in range(1, n):
		if (y1, y2) in a:
			res.append(a[y1, y2])
		elif (y2, y1) in a:
			res.append(a[y2, y1])
		else:
			rep = search(y1, y2, n)
			a[y1, y2] = rep
			res.append(rep)
	return res

def search(y1, y2, n):
	x = {}
	y = {}
	worklist = queue.Queue()
	worklist.put((0, 0))
	while worklist.qsize() != 0:
		b = worklist.get()
		if b in x:
			continue
		x[b] = True
		for k in compute(y1, y2, n, b):
			if solution(n, k) and k not in x:
				worklist.put(k)
				y[k] = b
			else:
				continue
	if (n - 1, n - 1) in x:
		res = sol(n, y)
		return res
	else:
		return -1

def compute(y1, y2, n, b):
	x1 = b[0]
	x2 = b[1]
	arr = []
	arr.append((x1 + y1, x2 + y2))
	arr.append((x1 + y1, x2 - y2))
	arr.append((x1 - y1, x2 + y2))
	arr.append((x1 - y1, x2 - y2))
	arr.append((x1 + y2, x2 + y1))
	arr.append((x1 + y2, x2 - y1))
	arr.append((x1 - y2, x2 + y1))
	arr.append((x1 - y2, x2 - y1))
	return arr

def sol(n, y):
	tot = 0
	b = (n - 1, n - 1)
	while b in y:
		p = y[b]
		tot = tot + 1
		if p == (0, 0):
			return tot
		else:
			b = p
n = int(input())
a = {}
for i in range(1, n):
	res = result(n, i, a)
	print(str(res)[1:-1].replace(',', ''))


import sys
n = int(input().strip())
m = [[-1 for x in range(n)] for y in range(n)]
g = 1
while g <= n - 1:
	d = 1
	while d <= n - 1:
		visited = []
		visited.append((n - 1, n - 1))
		counter = 0
		cur_len = 0
		diff = len(visited) - cur_len
		if m[g][d] == -1:
			while len(visited) > cur_len and (0, 0) not in visited:
				cur_len = len(visited)
				arr = visited[len(visited) - diff:len(visited)]
				h = 0
				while h <= len(arr) - 1:
					(t, r) = arr[h]
					if (t - g <= n - 1 and t - g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t - g, r - d) not in visited):
						visited.append((t - g, r - d))
					if (t - g <= n - 1 and t - g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t - g, r + d) not in visited):
						visited.append((t - g, r + d))
					if (t + g <= n - 1 and t + g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t + g, r - d) not in visited):
						visited.append((t + g, r - d))
					if (t + g <= n - 1 and t + g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t + g, r + d) not in visited):
						visited.append((t + g, r + d))
					if (t - d <= n - 1 and t - d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t - d, r - g) not in visited):
						visited.append((t - d, r - g))
					if (t - d <= n - 1 and t - d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t - d, r + g) not in visited):
						visited.append((t - d, r + g))
					if (t + d <= n - 1 and t + d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t + d, r - g) not in visited):
						visited.append((t + d, r - g))
					if (t + d <= n - 1 and t + d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t + d, r + g) not in visited):
						visited.append((t + d, r + g))
					h = h + 1
				diff = len(visited) - cur_len
				counter = counter + 1
			if (0, 0) in visited:
				m[g][d] = counter
				m[d][g] = m[g][d]
		d = d + 1
	g = g + 1
p = 1
while p <= n - 1:
	line = ''
	g = 1
	while g <= n - 1:
		line = line + ' ' + str(m[p][g])
		g = g + 1
	print(line.lstrip())
	p = p + 1


import sys
n = int(input().strip())

def possibles(i, j, x, y, n):
	p = []
	for c in range(-1, 2, 2):
		for d in range(-1, 2, 2):
			for (a, b) in [(i, j), (j, i)]:
				tx = x + a * c
				ty = y + b * d
				if tx >= 0 and tx < n and (ty >= 0) and (ty < n):
					p.append((tx, ty))
	return p

def dijkstra(a, b, tx, ty, n):
	x = 0
	y = 0
	visited = []
	toVisit = [(x, y)]
	distance = {(x, y): 0}
	while len(toVisit) > 0:
		current = toVisit[0]
		for node in possibles(a, b, current[0], current[1], n):
			if node not in visited and node not in toVisit:
				toVisit.append(node)
				distance[node] = distance[current] + 1
			else:
				distance[node] = min(distance[node], distance[current] + 1)
		toVisit.remove(current)
		visited.append(current)
	if (tx, ty) in distance:
		return distance[tx, ty]
	return -1
for a in range(1, n):
	for b in range(1, n):
		d = dijkstra(a, b, n - 1, n - 1, n)
		print(d, end=' ')
	print()


import sys
n = int(input().strip())

class Graph:

	def __init__(self, board_size, a, b):
		self.board_size = board_size
		nodes = [(x, y) for x in range(board_size) for y in range(board_size)]
		self.path_dict = {k: set() for k in nodes}
		for node in self.path_dict:
			self.path_dict[node] = {(node[0] + x, node[1] + y) for (x, y) in [(a, b), (-a, -b), (a, -b), (-a, b), (b, a), (-b, -a), (b, -a), (-b, a)] if 0 <= node[0] + x < board_size and 0 <= node[1] + y < board_size}

	def solution(self):
		distance = {(x, y): -1 for x in range(self.board_size) for y in range(self.board_size)}
		visited = {(self.board_size - 1, self.board_size - 1)}
		currentDistance = 0
		toVisitNext = self.path_dict[self.board_size - 1, self.board_size - 1]
		distance[self.board_size - 1, self.board_size - 1] = 0
		while len(toVisitNext) > 0:
			newDestinations = set()
			currentDistance += 1
			for node in toVisitNext:
				visited.add(node)
				distance[node] = currentDistance
				newDestinations |= self.path_dict[node]
			toVisitNext = set(newDestinations) - visited
		return distance[0, 0]
for a in range(1, n):
	row = ''
	for b in range(1, n):
		graph = Graph(n, a, b)
		row += str(graph.solution()) + ' '
	print(row.strip())


import sys
n = int(input().strip())

def getMoves(x, y, i):
	moves = []
	m1 = i + x + n * y
	m2 = i + x - n * y
	m3 = i - x + n * y
	m4 = i - x - n * y
	m5 = i + y + n * x
	m6 = i + y - n * x
	m7 = i - y + n * x
	m8 = i - y - n * x
	if i % n >= x:
		if y <= int(i / n):
			moves.append(m4)
		if y + int(i / n) < n:
			moves.append(m3)
	if i % n >= y:
		if x <= int(i / n):
			moves.append(m8)
		if x + int(i / n) < n:
			moves.append(m7)
	if i % n + x < n:
		if y <= int(i / n):
			moves.append(m2)
		if y + int(i / n) < n:
			moves.append(m1)
	if i % n + y < n:
		if x <= int(i / n):
			moves.append(m6)
		if x + int(i / n) < n:
			moves.append(m5)
	return moves

def shortestPath(start, end, x, y):
	found = False
	queue = [start]
	prev = {start: -1}
	visited = set()
	while len(queue) > 0:
		c = queue.pop(0)
		moves = getMoves(x, y, c)
		visited.add(c)
		if end in moves:
			found = True
			prev[end] = c
			break
		else:
			for u in moves:
				if u not in visited and u not in queue:
					queue.append(u)
					prev[u] = c
	if found:
		count = 0
		path = [end]
		x = end
		while x != -1:
			x = prev[x]
			path.append(x)
			count += 1
		return count - 1
	else:
		return -1
start = 0
end = n * n - 1
answer = []
for y in range(n):
	answer.append([-1] * n)
for y in range(n - 1):
	for x in range(n - 1):
		answer[x][y] = shortestPath(start, end, x + 1, y + 1)
		print(answer[x][y], end=' ')
	print('')


import sys
n = int(input().strip())

def get_moves(p, d):
	moves = set()
	for i in (d[0], -d[0]):
		for j in (d[1], -d[1]):
			x = p[0] + i
			y = p[1] + j
			move = (x, y)
			if 0 <= x < n and 0 <= y < n:
				moves.add((x, y))
	return moves

def make_move(p, d):
	m1 = get_moves(p, d)
	m2 = get_moves(p, d[::-1])
	poss = set.union(m1, m2)
	return poss

def get_to(init, dest, step):
	history = set()
	c = 0
	history.add(init)
	obs = [(init, c)]
	while obs:
		(point, cost) = obs.pop(0)
		np = make_move(point, step)
		for p in np:
			if p == dest:
				return cost + 1
			if not p in history:
				history.add(p)
				obs.append((p, cost + 1))
	return -1

def build_matrix(n):
	init = (0, 0)
	dest = (n - 1, n - 1)
	res = [[None for i in range(n - 1)] for j in range(n - 1)]
	for i in range(1, n):
		for j in range(1, i + 1):
			step = (i, j)
			cost = get_to(init, dest, step)
			res[i - 1][j - 1] = cost
			res[j - 1][i - 1] = cost
	for x in res:
		line = ' '.join([str(y) for y in x])
		print(line)

def test(num):
	from timeit import default_timer as timer
	t = timer()
	for i in range(num):
		build_matrix(n)
	print(timer() - t)
build_matrix(n)


def path_len(l_knight):
	board = []
	for n in range(N):
		board.append([-1] * N)
	(n, m) = l_knight
	(x, y) = [0, 0]

	def possible_moves(x, y, n, m):
		moves = []
		edge = len(board)
		xn_safe = x + n < edge
		xm_safe = x + m < edge
		ym_safe = y + m < edge
		yn_safe = y + n < edge
		ym0_safe = y - m >= 0
		yn0_safe = y - n >= 0
		xn0_safe = x - n >= 0
		xm0_safe = x - m >= 0
		if xn_safe and ym_safe:
			moves.append([x + n, y + m])
		if xn_safe and ym0_safe:
			moves.append([x + n, y - m])
		if xn0_safe and ym_safe:
			moves.append([x - n, y + m])
		if xn0_safe and ym0_safe:
			moves.append([x - n, y - m])
		if xm_safe and yn_safe:
			moves.append([x + m, y + n])
		if xm_safe and yn0_safe:
			moves.append([x + m, y - n])
		if xm0_safe and yn_safe:
			moves.append([x - m, y + n])
		if xm0_safe and yn0_safe:
			moves.append([x - m, y - n])
		return moves
	queue = []
	queue.append((x, y, 0))
	while len(queue) > 0:
		(x, y, moves) = queue.pop(0)
		if board[x][y] != -1 and moves >= board[x][y]:
			continue
		board[x][y] = moves
		next_moves = possible_moves(x, y, n, m)
		for next in next_moves:
			queue.append((next[0], next[1], moves + 1))
	return board[-1][-1]
N = int(input())
results = [0] * (N - 1)
diagonal_length = N - 1
for n in range(N - 1):
	results[n] = [0] * N
	for m in range(n + 1):
		l_knight = (n + 1, m + 1)
		if m == n and diagonal_length % (n + 1) == 0:
			path = int(diagonal_length / (m + 1))
		else:
			path = path_len(l_knight)
		results[n][m] = path
		results[m][n] = path
for n in range(len(results)):
	for m in range(len(results)):
		print(results[n][m], end=' ')
	print()


import sys
n = int(input().strip())
moves = [[0 for x in range(n - 1)] for y in range(n - 1)]
for i in range(1, n):
	for j in range(i, n):
		lookup = [[(0, 0)]]
		current = set()
		current.add((0, 0))
		unvisited = set()
		for k in range(n):
			for l in range(n):
				unvisited.add((k, l))
		unvisited.remove((0, 0))
		d = 0
		while len(unvisited) > 0:
			current = set()
			for loc in lookup[d]:
				if loc[0] + i < n and loc[1] + j < n and ((loc[0] + i, loc[1] + j) in unvisited):
					current.add((loc[0] + i, loc[1] + j))
				if loc[0] + i < n and loc[1] - j >= 0 and ((loc[0] + i, loc[1] - j) in unvisited):
					current.add((loc[0] + i, loc[1] - j))
				if loc[0] - i >= 0 and loc[1] + j < n and ((loc[0] - i, loc[1] + j) in unvisited):
					current.add((loc[0] - i, loc[1] + j))
				if loc[0] - i >= 0 and loc[1] - j >= 0 and ((loc[0] - i, loc[1] - j) in unvisited):
					current.add((loc[0] - i, loc[1] - j))
				if loc[0] + j < n and loc[1] + i < n and ((loc[0] + j, loc[1] + i) in unvisited):
					current.add((loc[0] + j, loc[1] + i))
				if loc[0] + j < n and loc[1] - i >= 0 and ((loc[0] + j, loc[1] - i) in unvisited):
					current.add((loc[0] + j, loc[1] - i))
				if loc[0] - j >= 0 and loc[1] + i < n and ((loc[0] - j, loc[1] + i) in unvisited):
					current.add((loc[0] - j, loc[1] + i))
				if loc[0] - j >= 0 and loc[1] - i >= 0 and ((loc[0] - j, loc[1] - i) in unvisited):
					current.add((loc[0] - j, loc[1] - i))
			if (n - 1, n - 1) in current:
				moves[i - 1][j - 1] = d + 1
				moves[j - 1][i - 1] = d + 1
				break
			if current == set():
				moves[i - 1][j - 1] = -1
				moves[j - 1][i - 1] = -1
				break
			unvisited -= current
			lookup.append(current)
			d += 1
for a in moves:
	for b in a:
		print(b, end=' ')
	print()


n = int(input().strip())
pairs = []
(start, end) = ((0, 0), (n - 1, n - 1))

def validPos(pos):
	return pos[0] >= 0 and pos[1] >= 0 and (pos[0] < n) and (pos[1] < n)

def moves(x, pair):
	moves = []
	(a, b) = (pair[0], pair[1])
	(x1, x2) = (x[0], x[1])
	moves.append((x1 + a, x2 + b))
	moves.append((x1 + a, x2 - b))
	moves.append((x1 - a, x2 + b))
	moves.append((x1 - a, x2 - b))
	moves.append((x1 + b, x2 + a))
	moves.append((x1 + b, x2 - a))
	moves.append((x1 - b, x2 + a))
	moves.append((x1 - b, x2 - a))
	return set(filter(validPos, moves))

def minPath(pair):
	old_moves = [start]
	new_moves = moves(start, pair)
	count = 1
	while len(new_moves) > 0 and end not in new_moves:
		count += 1
		for move in new_moves.copy():
			if move not in old_moves:
				old_moves.append(move)
				new_moves.remove(move)
				for m in moves(move, pair):
					if m not in old_moves:
						new_moves.add(m)
	if len(new_moves) == 0:
		return -1
	else:
		return count
for i in range(1, n):
	print(*[minPath((i, j)) for j in range(1, n)], sep=' ')


import sys
n = int(input().strip())
target = (n - 1, n - 1)

def knightL(x, y, n, target):
	v = 1
	pos = [(x, y, v), (x, y, v)]
	visited = set([(0, 0)])
	fine = []
	while pos != []:
		i = pos.pop(0)
		if i[:2] == target:
			fine.append(i[2])
		if i[:2] in visited:
			continue
		if i[0] + x < n and i[1] + y < n:
			pos.append((i[0] + x, i[1] + y, i[2] + 1))
		if i[0] + x < n and i[1] - y >= 0:
			pos.append((i[0] + x, i[1] - y, i[2] + 1))
		if i[0] - x >= 0 and i[1] + y < n:
			pos.append((i[0] - x, i[1] + y, i[2] + 1))
		if i[0] - x >= 0 and i[1] - y >= 0:
			pos.append((i[0] - x, i[1] - y, i[2] + 1))
		if i[0] + y < n and i[1] + x < n:
			pos.append((i[0] + y, i[1] + x, i[2] + 1))
		if i[0] + y < n and i[1] - x >= 0:
			pos.append((i[0] + y, i[1] - x, i[2] + 1))
		if i[0] - y >= 0 and i[1] + x < n:
			pos.append((i[0] - y, i[1] + x, i[2] + 1))
		if i[0] - y >= 0 and i[1] - x >= 0:
			pos.append((i[0] - y, i[1] - x, i[2] + 1))
		visited.add(i[:2])
	if len(fine) > 0:
		return min(fine)
	else:
		return -1
results = []
for i in range(n - 1):
	results.append([])
	for j in range(n - 1):
		results[i].append(0)
for i in range(1, n):
	for j in range(i, n):
		results[i - 1][j - 1] = results[j - 1][i - 1] = knightL(i, j, n, target)
for i in range(n - 1):
	for j in range(n - 1):
		print(results[i][j], end=' ')
	print()


import sys
o = int(input().strip())
ans = [[[4, 4, 2, 8], [4, 2, 4, 4], [2, 4, -1, -1], [8, 4, -1, 1]], [[5, 4, 3, 2, 5], [4, -1, 2, -1, -1], [3, 2, -1, -1, -1], [2, -1, -1, -1, -1], [5, -1, -1, -1, 1]], [[6, 4, 4, 8, 2, 12], [4, 3, 4, 2, 16, 3], [4, 4, 2, 4, 4, 4], [8, 2, 4, -1, -1, -1], [2, 16, 4, -1, -1, -1], [12, 3, 4, -1, -1, 1]], [[7, 6, 5, 6, 5, 2, 7], [6, -1, 6, -1, 2, -1, -1], [5, 6, -1, 2, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1], [5, 2, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1], [7, -1, -1, -1, -1, -1, 1]], [[8, 6, 4, 4, 6, 12, 2, 16], [6, 4, 6, 4, 8, 2, 8, 8], [4, 6, -1, 4, 2, -1, -1, -1], [4, 4, 4, 2, 4, 4, 4, 4], [6, 8, 2, 4, -1, -1, -1, -1], [12, 2, -1, 4, -1, -1, -1, -1], [2, 8, -1, 4, -1, -1, -1, -1], [16, 8, -1, 4, -1, -1, -1, 1]], [[9, 6, 5, 8, 5, 6, 7, 2, 9], [6, -1, 6, -1, 10, -1, 2, -1, -1], [5, 6, 3, 6, 7, 2, 13, -1, 3], [8, -1, 6, -1, 2, -1, -1, -1, -1], [5, 10, 7, 2, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1], [7, 2, 13, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1], [9, -1, 3, -1, -1, -1, -1, -1, 1]], [[10, 8, 6, 4, 4, 8, 6, 16, 2, 20], [8, 5, 4, 4, 4, 3, 8, 2, 28, 5], [6, 4, -1, 8, 4, -1, 2, 16, -1, -1], [4, 4, 8, -1, 4, 2, -1, -1, -1, -1], [4, 4, 4, 4, 2, 4, 4, 4, 4, 4], [8, 3, -1, 2, 4, -1, -1, -1, -1, -1], [6, 8, 2, -1, 4, -1, -1, -1, -1, -1], [16, 2, 16, -1, 4, -1, -1, -1, -1, -1], [2, 28, -1, -1, 4, -1, -1, -1, -1, -1], [20, 5, -1, -1, 4, -1, -1, -1, -1, 1]], [[11, 8, 7, 6, 7, 10, 7, 6, 9, 2, 11], [8, -1, 6, -1, 6, -1, 14, -1, 2, -1, -1], [7, 6, -1, 8, 7, -1, 7, 2, -1, -1, -1], [6, -1, 8, -1, 6, -1, 2, -1, -1, -1, -1], [7, 6, 7, 6, -1, 2, -1, -1, -1, -1, -1], [10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1], [7, 14, 7, 2, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[12, 8, 6, 8, 4, 4, 8, 12, 6, 20, 2, 24], [8, 6, 6, 4, 10, 4, 12, 8, 12, 2, 12, 12], [6, 6, 4, 8, 6, 4, 8, 8, 2, 8, 8, 8], [8, 4, 8, 3, 8, 4, 12, 2, 36, 16, -1, 3], [4, 10, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4], [8, 12, 8, 12, 2, 4, -1, -1, -1, -1, -1, -1], [12, 8, 8, 2, -1, 4, -1, -1, -1, -1, -1, -1], [6, 12, 2, 36, -1, 4, -1, -1, -1, -1, -1, -1], [20, 2, 8, 16, -1, 4, -1, -1, -1, -1, -1, -1], [2, 12, 8, -1, -1, 4, -1, -1, -1, -1, -1, -1], [24, 12, 8, 3, -1, 4, -1, -1, -1, -1, -1, 1]], [[13, 10, 7, 6, 5, 12, 7, 10, 9, 6, 11, 2, 13], [10, -1, 6, -1, 6, -1, 6, -1, 18, -1, 2, -1, -1], [7, 6, -1, 6, 7, -1, 9, 14, -1, 2, -1, -1, -1], [6, -1, 6, -1, 10, -1, 10, -1, 2, -1, -1, -1, -1], [5, 6, 7, 10, -1, 6, 11, 2, -1, -1, -1, -1, -1], [12, -1, -1, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1], [7, 6, 9, 10, 11, 2, -1, -1, -1, -1, -1, -1, -1], [10, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 18, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[14, 10, 8, 8, 6, 4, 4, 8, 10, 16, 6, 24, 2, 28], [10, 7, 8, 6, 4, 5, 4, 6, 8, 5, 12, 2, 40, 7], [8, 8, -1, 4, 6, -1, 4, 16, -1, 8, 2, -1, -1, -1], [8, 6, 4, -1, 10, 6, 4, -1, 20, 2, 16, -1, -1, -1], [6, 4, 6, 10, -1, 8, 4, 12, 2, -1, -1, -1, -1, -1], [4, 5, -1, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4], [8, 6, 16, -1, 12, 2, 4, -1, -1, -1, -1, -1, -1, -1], [10, 8, -1, 20, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1], [16, 5, 8, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [6, 12, 2, 16, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [24, 2, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [2, 40, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [28, 7, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, 1]], [[15, 10, 9, 6, 7, 10, 9, 14, 9, 10, 11, 6, 13, 2, 15], [10, -1, 6, -1, 10, -1, 10, -1, 6, -1, 22, -1, 2, -1, -1], [9, 6, 5, 6, 5, 4, 7, 10, 3, 14, 13, 2, 23, -1, 5], [6, -1, 6, -1, 10, -1, 14, -1, 10, -1, 2, -1, -1, -1, -1], [7, 10, 5, 10, 3, 10, 9, 14, 13, 2, 23, -1, -1, -1, 3], [10, -1, 4, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1], [9, 10, 7, 14, 9, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1], [14, -1, 10, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 6, 3, 10, 13, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 22, 13, 2, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 2, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, -1, 5, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[16, 12, 8, 8, 6, 8, 4, 4, 8, 12, 10, 20, 6, 28, 2, 32], [12, 8, 8, 6, 8, 4, 14, 4, 16, 6, 16, 12, 16, 2, 16, 16], [8, 8, -1, 8, 4, -1, 6, 4, -1, 20, 8, -1, 2, 28, -1, -1], [8, 6, 8, 4, 8, 6, 8, 4, 8, 8, 8, 2, 8, 8, 8, 8], [6, 8, 4, 8, -1, 12, 6, 4, 10, -1, 2, 68, 16, -1, -1, -1], [8, 4, -1, 6, 12, -1, 8, 4, -1, 2, -1, -1, -1, -1, -1, -1], [4, 14, 6, 8, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4], [8, 16, -1, 8, 10, -1, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1], [12, 6, 20, 8, -1, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [10, 16, 8, 8, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [20, 12, -1, 2, 68, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [6, 16, 2, 8, 16, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [28, 2, 28, 8, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [2, 16, -1, 8, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [32, 16, -1, 8, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, 1]], [[17, 12, 9, 8, 7, 6, 7, 16, 9, 14, 11, 10, 13, 6, 15, 2, 17], [12, -1, 8, -1, 6, -1, 10, -1, 14, -1, 6, -1, 26, -1, 2, -1, -1], [9, 8, -1, 8, 5, -1, 9, 6, -1, 18, 13, -1, 13, 2, -1, -1, -1], [8, -1, 8, -1, 6, -1, 6, -1, 18, -1, 14, -1, 2, -1, -1, -1, -1], [7, 6, 5, 6, -1, 12, 11, 10, 9, -1, 13, 2, -1, -1, -1, -1, -1], [6, -1, -1, -1, 12, -1, 10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1], [7, 10, 9, 6, 11, 10, -1, 6, 15, 2, -1, -1, -1, -1, -1, -1, -1], [16, -1, 6, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 14, -1, 18, 9, -1, 15, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 18, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 6, 13, 14, 13, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 26, 13, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[18, 12, 10, 8, 6, 12, 8, 4, 4, 8, 12, 16, 10, 24, 6, 32, 2, 36], [12, 9, 8, 6, 8, 5, 4, 8, 4, 5, 8, 6, 12, 7, 16, 2, 52, 9], [10, 8, 6, 8, 6, 4, 6, 12, 4, 12, 12, 8, 12, 12, 2, 12, 12, 12], [8, 6, 8, -1, 4, 6, 14, -1, 4, 10, 20, -1, 8, 2, -1, -1, -1, -1], [6, 8, 6, 4, -1, 12, 8, 16, 4, -1, 10, 20, 2, 16, -1, -1, -1, -1], [12, 5, 4, 6, 12, 3, 12, 6, 4, 7, 24, 2, 56, 13, 16, -1, -1, 3], [8, 4, 6, 14, 8, 12, -1, 8, 4, 20, 2, -1, -1, -1, -1, -1, -1, -1], [4, 8, 12, -1, 16, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 5, 12, 10, -1, 7, 20, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, 12, 20, 10, 24, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [16, 6, 8, -1, 20, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 12, 12, 8, 2, 56, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [24, 7, 12, 2, 16, 13, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 16, 2, -1, -1, 16, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [32, 2, 12, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 52, 12, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [36, 9, 12, -1, -1, 3, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[19, 14, 11, 10, 7, 6, 7, 14, 11, 18, 11, 14, 13, 10, 15, 6, 17, 2, 19], [14, -1, 10, -1, 10, -1, 6, -1, 10, -1, 18, -1, 6, -1, 30, -1, 2, -1, -1], [11, 10, -1, 10, 7, -1, 7, 16, -1, 6, 11, -1, 15, 22, -1, 2, -1, -1, -1], [10, -1, 10, -1, 6, -1, 6, -1, 14, -1, 22, -1, 14, -1, 2, -1, -1, -1, -1], [7, 10, 7, 6, -1, 10, 11, 6, 13, -1, 13, 26, 17, 2, -1, -1, -1, -1, -1], [6, -1, -1, -1, 10, -1, 14, -1, -1, -1, 10, -1, 2, -1, -1, -1, -1, -1, -1], [7, 6, 7, 6, 11, 14, -1, 10, 13, 14, 17, 2, -1, -1, -1, -1, -1, -1, -1], [14, -1, 16, -1, 6, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [11, 10, -1, 14, 13, -1, 13, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, -1, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 18, 11, 22, 13, 10, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, -1, -1, 26, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 6, 15, 14, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 30, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[20, 14, 10, 8, 8, 12, 6, 8, 4, 4, 8, 12, 14, 20, 10, 28, 6, 36, 2, 40], [14, 10, 8, 8, 8, 6, 12, 4, 18, 4, 20, 8, 20, 6, 20, 16, 20, 2, 20, 20], [10, 8, -1, 8, 8, -1, 4, 12, -1, 4, 6, -1, 8, 28, -1, 12, 2, -1, -1, -1], [8, 8, 8, 5, 8, 4, 8, 4, 12, 4, 16, 3, 20, 8, 24, 2, 64, 28, -1, 5], [8, 8, 8, 8, 4, 8, 8, 8, 8, 4, 8, 8, 8, 8, 2, 8, 8, 8, 8, 8], [12, 6, -1, 4, 8, -1, 14, 8, -1, 4, 12, -1, 32, 2, -1, 16, -1, -1, -1, -1], [6, 12, 4, 8, 8, 14, -1, 12, 6, 4, 12, 12, 2, -1, -1, -1, -1, -1, -1, -1], [8, 4, 12, 4, 8, 8, 12, -1, 8, 4, 20, 2, -1, -1, -1, -1, -1, -1, -1, -1], [4, 18, -1, 12, 8, -1, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 20, 6, 16, 8, 12, 12, 20, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, -1, 3, 8, -1, 12, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, 20, 8, 20, 8, 32, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [20, 6, 28, 8, 8, 2, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 20, -1, 24, 2, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [28, 16, 12, 2, 8, 16, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 20, 2, 64, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [36, 2, -1, 28, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 20, -1, -1, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [40, 20, -1, 5, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[21, 14, 11, 10, 9, 6, 9, 10, 9, 20, 11, 18, 13, 14, 15, 10, 17, 6, 19, 2, 21], [14, -1, 10, -1, 6, -1, 14, -1, 10, -1, 10, -1, 22, -1, 6, -1, 34, -1, 2, -1, -1], [11, 10, 7, 6, 9, 6, 7, 6, 5, 10, 11, 6, 13, 18, 5, 22, 19, 2, 33, -1, 7], [10, -1, 6, -1, 10, -1, 14, -1, 6, -1, 10, -1, 26, -1, 18, -1, 2, -1, -1, -1, -1], [9, 6, 9, 10, -1, 6, 9, 16, 9, -1, 15, 10, 15, 14, -1, 2, -1, -1, -1, -1, -1], [6, -1, 6, -1, 6, -1, 14, -1, 6, -1, 18, -1, 10, -1, 2, -1, -1, -1, -1, -1, -1], [9, 14, 7, 14, 9, 14, 3, 14, 13, 18, 15, 22, 19, 2, 33, -1, -1, -1, -1, -1, 3], [10, -1, 6, -1, 16, -1, 14, -1, 10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 10, 5, 6, 9, 6, 13, 10, -1, 6, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [20, -1, 10, -1, -1, -1, 18, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 10, 11, 10, 15, 18, 15, 22, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, 10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 22, 13, 26, 15, 10, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 18, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 6, 5, 18, -1, 2, 33, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 34, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, 2, 33, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [21, -1, 7, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[22, 16, 12, 10, 8, 8, 6, 12, 8, 4, 4, 8, 12, 16, 14, 24, 10, 32, 6, 40, 2, 44], [16, 11, 10, 8, 10, 7, 8, 6, 4, 7, 4, 10, 8, 7, 12, 6, 16, 9, 20, 2, 64, 11], [12, 10, -1, 8, 8, -1, 8, 4, -1, 16, 4, -1, 6, 8, -1, 32, 12, -1, 2, 40, -1, -1], [10, 8, 8, -1, 10, 6, 4, -1, 18, 6, 4, -1, 24, 14, 8, -1, 32, 2, 28, -1, -1, -1], [8, 10, 8, 10, -1, 4, 6, 8, 6, -1, 4, 24, 14, 20, -1, 8, 2, -1, -1, -1, -1, -1], [8, 7, -1, 6, 4, -1, 12, 8, -1, 7, 4, -1, 20, 7, -1, 2, 16, -1, -1, -1, -1, -1], [6, 8, 8, 4, 6, 12, -1, 16, 8, 12, 4, 20, 10, -1, 2, 36, -1, 16, -1, -1, -1, -1], [12, 6, 4, -1, 8, 8, 16, -1, 12, 6, 4, -1, 12, 2, -1, -1, -1, -1, -1, -1, -1, -1], [8, 4, -1, 18, 6, -1, 8, 12, -1, 8, 4, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 7, 16, 6, -1, 7, 12, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 10, -1, -1, 24, -1, 20, -1, -1, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, 6, 24, 14, 20, 10, 12, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [16, 7, 8, 14, 20, 7, -1, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, 12, -1, 8, -1, -1, 2, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [24, 6, 32, -1, 8, 2, 36, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 16, 12, 32, 2, 16, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [32, 9, -1, 2, -1, -1, 16, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 20, 2, 28, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [40, 2, 40, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 64, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [44, 11, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[23, 16, 13, 10, 9, 10, 9, 6, 9, 18, 13, 22, 13, 18, 15, 14, 17, 10, 19, 6, 21, 2, 23], [16, -1, 10, -1, 10, -1, 6, -1, 14, -1, 14, -1, 10, -1, 26, -1, 6, -1, 38, -1, 2, -1, -1], [13, 10, -1, 10, 7, -1, 9, 10, -1, 20, 11, -1, 13, 6, -1, 26, 19, -1, 19, 2, -1, -1, -1], [10, -1, 10, -1, 10, -1, 10, -1, 6, -1, 6, -1, 18, -1, 30, -1, 18, -1, 2, -1, -1, -1, -1], [9, 10, 7, 10, -1, 6, 7, 6, 13, -1, 11, 14, 17, 26, -1, 14, 21, 2, -1, -1, -1, -1, -1], [10, -1, -1, -1, 6, -1, 10, -1, -1, -1, 22, -1, 18, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1], [9, 6, 9, 10, 7, 10, -1, 16, 15, 6, 11, 10, 15, -1, 19, 2, 55, -1, -1, -1, -1, -1, -1], [6, -1, 10, -1, 6, -1, 16, -1, 14, -1, 14, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 14, -1, 6, 13, -1, 15, 14, -1, 10, 17, -1, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 20, -1, -1, -1, 6, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 14, 11, 6, 11, 22, 11, 14, 17, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [22, -1, -1, -1, 14, -1, 10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 10, 13, 18, 17, 18, 15, 22, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, 26, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 26, -1, 30, -1, -1, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 26, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 6, 19, 18, 21, 2, 55, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, 38, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [21, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[24, 16, 12, 12, 8, 8, 6, 16, 10, 8, 4, 4, 8, 12, 16, 20, 14, 28, 10, 36, 6, 44, 2, 48], [16, 12, 12, 8, 8, 6, 8, 8, 16, 4, 22, 4, 24, 8, 24, 12, 24, 6, 24, 20, 24, 2, 24, 24], [12, 12, 8, 8, 6, 6, 6, 16, 4, 16, 10, 4, 14, 16, 6, 16, 16, 12, 16, 16, 2, 16, 16, 16], [12, 8, 8, 6, 12, 6, 12, 4, 12, 10, 12, 4, 12, 12, 12, 8, 12, 12, 12, 2, 12, 12, 12, 12], [8, 8, 6, 12, -1, 8, 4, 16, 6, -1, 12, 4, 10, 28, -1, 20, 8, 24, 2, -1, -1, -1, -1, -1], [8, 6, 6, 6, 8, 4, 8, 8, 6, 6, 8, 4, 8, 8, 8, 8, 8, 2, 8, 8, 8, 8, 8, 8], [6, 8, 6, 12, 4, 8, -1, 16, 10, 20, 10, 4, 12, -1, 10, 20, 2, -1, 16, -1, -1, -1, -1, -1], [16, 8, 16, 4, 16, 8, 16, 3, 16, 8, 20, 4, 24, 12, 36, 2, 76, 36, -1, 16, -1, -1, -1, 3], [10, 16, 4, 12, 6, 6, 10, 16, -1, 12, 6, 4, 14, 32, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [8, 4, 16, 10, -1, 6, 20, 8, 12, -1, 8, 4, 24, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 22, 10, 12, 12, 8, 10, 20, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 24, 14, 12, 10, 8, 12, 24, 14, 24, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, 16, 12, 28, 8, -1, 12, 32, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [16, 24, 6, 12, -1, 8, 10, 36, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [20, 12, 16, 8, 20, 8, 20, 2, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, 24, 16, 12, 8, 8, 2, 76, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [28, 6, 12, 12, 24, 2, -1, 36, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 24, 16, 12, 2, 8, 16, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [36, 20, 16, 2, -1, 8, -1, 16, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 24, 2, 12, -1, 8, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [44, 2, 16, 12, -1, 8, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 24, 16, 12, -1, 8, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [48, 24, 16, 12, -1, 8, -1, 3, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[25, 18, 13, 10, 9, 12, 7, 6, 9, 14, 11, 24, 13, 22, 15, 18, 17, 14, 19, 10, 21, 6, 23, 2, 25], [18, -1, 10, -1, 10, -1, 14, -1, 6, -1, 14, -1, 18, -1, 10, -1, 30, -1, 6, -1, 42, -1, 2, -1, -1], [13, 10, -1, 8, 7, -1, 7, 14, -1, 10, 13, -1, 13, 26, -1, 6, 17, -1, 21, 30, -1, 2, -1, -1, -1], [10, -1, 8, -1, 10, -1, 6, -1, 14, -1, 18, -1, 6, -1, 14, -1, 34, -1, 22, -1, 2, -1, -1, -1, -1], [9, 10, 7, 10, 5, 10, 7, 10, 9, 4, 11, 18, 13, 22, 3, 26, 19, 30, 23, 2, 41, -1, -1, -1, 5], [12, -1, -1, -1, 10, -1, 6, -1, -1, -1, 14, -1, 26, -1, -1, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1], [7, 14, 7, 6, 7, 6, -1, 14, 15, 10, 17, 14, 15, -1, 19, 38, 21, 2, -1, -1, -1, -1, -1, -1, -1], [6, -1, 14, -1, 10, -1, 14, -1, 18, -1, 6, -1, 14, -1, 10, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 6, -1, 14, 9, -1, 15, 18, -1, 14, 15, -1, 17, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 10, -1, 4, -1, 10, -1, 14, -1, 10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 14, 13, 18, 11, 14, 17, 6, 15, 10, -1, 6, 23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [24, -1, -1, -1, 18, -1, 14, -1, -1, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 18, 13, 6, 13, 26, 15, 14, 17, 22, 23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [22, -1, 26, -1, 22, -1, -1, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 10, -1, 14, 3, -1, 19, 10, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, 26, -1, 38, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 30, 17, 34, 19, 14, 21, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, -1, -1, 30, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, 6, 21, 22, 23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 30, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [21, 42, -1, 2, 41, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [25, -1, -1, -1, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]]]
for i in range(0, o - 1):
	for j in range(0, o - 1):
		print(ans[o - 5][i][j], end=' ')
	print('')


from collections import deque

def _neighbor(a, b, pos):
	(x, y) = pos
	for i in [-a, a]:
		for j in [-b, b]:
			yield (x + i, y + j)
			yield (x + j, y + i)

def inbounds(pos, n):
	(x, y) = pos
	return 0 <= x < n and 0 <= y < n

def neighbor(a, b, pos, n):
	for newpos in _neighbor(a, b, pos):
		if inbounds(newpos, n):
			yield newpos

def find_path_length(a, b, n):
	q = deque()
	parent_of = dict()
	q.append((0, 0))
	while q:
		v = q.popleft()
		if v == (n - 1, n - 1):
			break
		for u in neighbor(a, b, v, n):
			if u not in parent_of:
				parent_of[u] = v
				q.append(u)
	length = -1
	v = (n - 1, n - 1)
	while v != (0, 0) and v in parent_of:
		length += 1
		v = parent_of[v]
	return length + 1 if length != -1 else -1

def solve():
	n = int(input())
	out = [[0] * n for i in range(n)]
	for a in range(1, n):
		for b in range(a, n):
			out[a][b] = find_path_length(a, b, n)
			out[b][a] = out[a][b]
	for a in range(1, n):
		for b in range(1, n):
			print(out[a][b], end=' ')
		print()
solve()


import sys
n = int(input().strip())

def twoIntToString(i1, i2):
	return str(i1) + ',' + str(i2)

def stringToTwo(couple):
	return list(map(int, couple.split(',')))

def nextSquares(x, y, a, b, n):
	validSquares = []
	if x + a < n and y + b < n:
		validSquares.append(twoIntToString(x + a, y + b))
	if x + b < n and y + a < n:
		validSquares.append(twoIntToString(x + b, y + a))
	if x + a < n and y - b >= 0:
		validSquares.append(twoIntToString(x + a, y - b))
	if x + b < n and y - a >= 0:
		validSquares.append(twoIntToString(x + b, y - a))
	if x - a >= 0 and y - b >= 0:
		validSquares.append(twoIntToString(x - a, y - b))
	if x - b >= 0 and y - a >= 0:
		validSquares.append(twoIntToString(x - b, y - a))
	if x - a >= 0 and y + b < n:
		validSquares.append(twoIntToString(x - a, y + b))
	if x - b >= 0 and y + a < n:
		validSquares.append(twoIntToString(x - b, y + a))
	return validSquares
res = ''
for a in range(1, n):
	for b in range(1, n):
		squareValue = {'0,0': 0}
		squareToVisit = ['0,0']
		temp = []
		giro = 1
		while True:
			squareToVisit = list(map(stringToTwo, squareToVisit))
			for couple in squareToVisit:
				validSquares = nextSquares(couple[0], couple[1], a, b, n)
				for square in validSquares:
					if square not in squareValue:
						squareValue[square] = giro
						temp.append(square)
			squareToVisit = temp
			temp = []
			giro += 1
			if str(n - 1) + ',' + str(n - 1) in squareValue:
				res += str(squareValue[str(n - 1) + ',' + str(n - 1)]) + ' '
				break
			if squareToVisit == []:
				res += str(-1) + ' '
				break
	print(res)
	res = ''


import sys

def valid_move_combine(start, dpos, n):
	end = (start[0] + dpos[0], start[1] + dpos[1])
	if end[0] >= 0 and end[0] < n and (end[1] >= 0) and (end[1] < n):
		return end
	else:
		return None

def KnightL(a, b, n):
	halfMoves = [(a, b), (-a, b), (a, -b), (-a, -b)]
	moves = halfMoves + [(y, x) for (x, y) in halfMoves]
	moves = set(moves)
	Q = []
	start = (0, 0)
	end = (n - 1, n - 1)
	Q.append([start])
	visited = set()
	while Q:
		path = Q.pop(0)
		node = path[-1]
		if node == end:
			return path
		if node not in visited:
			visited.add(node)
			for dpos in moves:
				adj = valid_move_combine(node, dpos, n)
				if adj:
					Q.append(path + [adj])
	return None
n = int(input().strip())
for a in range(1, n):
	res = []
	for b in range(1, n):
		temp = KnightL(a, b, n)
		if temp:
			res.append(len(temp) - 1)
		else:
			res.append(-1)
	print(*res, sep=' ')


n = int(input().strip())
e = n ** 2 - 1

def moves(s, a, b, n):
	c = set()
	(xs, ys) = (s % n, s // n)
	m = [(xs + a, ys + b), (xs + a, ys - b), (xs - a, ys + b), (xs - a, ys - b), (xs + b, ys + a), (xs + b, ys - a), (xs - b, ys + a), (xs - b, ys - a)]
	for (x, y) in m:
		if 0 <= x < n and 0 <= y < n:
			c |= {x + n * y}
	return c

def explore(g, s, a, b, n):
	if s not in g:
		m = moves(s, a, b, n)
		g[s] = m
		for c in m:
			explore(g, c, a, b, n)

def dijkstra(g, s):
	q = list(g.keys())
	d = {k: len(q) for k in q}
	d[s] = 0
	p = {k: None for k in q}
	while q != []:
		qd = sorted([(n, d[n]) for n in q], key=lambda x: x[1])
		(u, du) = qd[0]
		q.remove(u)
		for v in g[u]:
			if v in q:
				dv = du + 1
				if dv < d[v]:
					d[v] = dv
					p[v] = u
	return (d, p)

def route(p, e):
	path = []
	u = e
	while p[u] is not None:
		path.insert(0, u)
		u = p[u]
	path.insert(0, u)
	return path
for a in range(1, n):
	for b in range(1, n):
		g = {}
		explore(g, 0, a, b, n)
		if e not in g:
			r = -1
		else:
			(d, p) = dijkstra(g, 0)
			r = len(route(p, e)) - 1
		print(r, end=' ')
	print()


import sys
from queue import Queue

def next_valid_cells(visited, x, y, a_delta, b_delta, n):
	valid_cells = []
	up = x - a_delta
	down = x + a_delta
	left = y - b_delta
	right = y + b_delta
	if (up >= 0 and left >= 0) and (up, left) not in visited:
		valid_cells.append((up, left))
		visited.add((up, left))
	if (up >= 0 and right < n) and (up, right) not in visited:
		valid_cells.append((up, right))
		visited.add((up, right))
	if (down < n and left >= 0) and (down, left) not in visited:
		valid_cells.append((down, left))
		visited.add((down, left))
	if (down < n and right < n) and (down, right) not in visited:
		valid_cells.append((down, right))
		visited.add((down, right))
	return valid_cells

def breadth_first_search(a_delta, b_delta, n):
	visited = set()
	q = Queue()
	q.put([(0, 0), 0])
	while q.empty() == False:
		((curr_x, curr_y), depth) = q.get()
		if curr_x == n - 1 and curr_y == n - 1:
			return depth
		next_cells = next_valid_cells(visited, curr_x, curr_y, a_delta, b_delta, n)
		next_cells += next_valid_cells(visited, curr_x, curr_y, b_delta, a_delta, n)
		for cell in next_cells:
			if cell == (n - 1, n - 1):
				return depth + 1
			q.put([cell, depth + 1])
	return -1

def main():
	n = int(input().strip())
	final_result = [['-1'] * (n - 1) for _ in range(n - 1)]
	for outer in range(1, n):
		for inner in range(outer, n):
			if inner == 1 and outer == 1:
				final_result[0][0] = str(n - 1)
			elif inner == n - 1 and outer == n - 1:
				final_result[inner - 1][outer - 1] = '1'
			else:
				r = str(breadth_first_search(outer, inner, n))
				final_result[inner - 1][outer - 1] = r
				final_result[outer - 1][inner - 1] = r
	for row in final_result:
		print(' '.join(row))
main()


import sys
display = False

def getChoices(curr, a, b, n1):
	if display:
		print('bgn getChoices curr:', curr)
	result = set()
	limits = range(n1 + 1)
	(x, y) = (curr // 30, curr % 30)
	(al, bl) = ([a, a, -a, -a, b, b, -b, -b], [b, -b, b, -b, a, -a, a, -a])
	xn = [i + x if i + x in limits else -99 for i in al]
	yn = [i + y if i + y in limits else -99 for i in bl]
	result = {30 * xn[i] + yn[i] for i in range(8) if xn[i] in limits and yn[i] in limits}
	if display:
		print('end getChoices result:', result)
	return result

def mincalc(a, b, n1):
	if display:
		print('bgn mincalc a:', a, ' b:', b, ' n1:', n1)
	result = 0
	target = 31 * n1
	found = False
	moves = set()
	choices = {0}
	while len(choices - moves) and (not found):
		choices -= moves
		if display:
			print('moves:', *moves)
			print('choices:', *choices)
		nxtchoices = set()
		for choice in choices:
			moves.add(choice)
			nxtchoices = nxtchoices | getChoices(choice, a, b, n1)
			if target in nxtchoices:
				found = True
				break
		result += 1
		choices = nxtchoices
		if display:
			print('nxtchoices:', *choices)
	if not found:
		result = -1
	if display:
		print('end mincalc result:', result)
	return result
n = int(input().strip())
n1 = n - 1
mx = [[0 for x in range(n1)] for y in range(n1)]
for i in range(n1):
	for j in range(i, n1):
		if False and i == 1 and (j == 9):
			display = True
		else:
			display = False
		mx[i][j] = mincalc(i + 1, j + 1, n1)
for i in range(n1):
	for j in range(0, i):
		mx[i][j] = mx[j][i]
for row in mx:
	for cell in row:
		print(cell, end=' ')
	print()


import sys
n = int(input().strip())

def find_reachable_squares(x, y, a, b, n):
	squares = set()
	if x + a >= 0 and x + a < n:
		if y + b >= 0 and y + b < n:
			squares.add((x + a, y + b))
		if y - b >= 0 and y - b < n:
			squares.add((x + a, y - b))
	if x - a >= 0 and x - a < n:
		if y + b >= 0 and y + b < n:
			squares.add((x - a, y + b))
		if y - b >= 0 and y - b < n:
			squares.add((x - a, y - b))
	if x + b >= 0 and x + b < n:
		if y + a >= 0 and y + a < n:
			squares.add((x + b, y + a))
		if y - a >= 0 and y - a < n:
			squares.add((x + b, y - a))
	if x - b >= 0 and x - b < n:
		if y + a >= 0 and y + a < n:
			squares.add((x - b, y + a))
		if y - a >= 0 and y - a < n:
			squares.add((x - b, y - a))
	return squares
matrix = [[0 for x in range(n - 1)] for y in range(n - 1)]
for i in range(1, n):
	for j in range(i, n):
		reachable_squares = set([(n - 1, n - 1)])
		previous_squares = set([(n - 1, n - 1)])
		history_sq = set([(n - 1, n - 1)])
		count = 0
		while len(reachable_squares) > 0 and (0, 0) not in history_sq:
			reachable_squares = set()
			count = count + 1
			for s in previous_squares:
				reachable_squares = reachable_squares | find_reachable_squares(s[0], s[1], i, j, n)
			reachable_squares = reachable_squares - history_sq
			previous_squares = set()
			for s in reachable_squares:
				previous_squares.add(s)
				history_sq.add(s)
		val = -1
		if (0, 0) in history_sq:
			val = count
		matrix[i - 1][j - 1] = val
		matrix[j - 1][i - 1] = val
for i in matrix:
	string = ''
	for j in i:
		string = string + ' ' + str(j)
	print(string[1:])


import sys
from collections import deque
n = int(input().strip())
for i in range(1, n):
	curans = []
	for j in range(1, n):
		goal = False
		di = {(0, 0): 0}
		valid = False
		q = deque()
		q.append((0, 0))
		tried = set()
		while not goal:
			valid = False
			temp = q.popleft()
			if temp[0] - i >= 0:
				if temp[1] - j >= 0:
					if (temp[0] - i, temp[1] - j) not in tried:
						q.append((temp[0] - i, temp[1] - j))
						tried.add((temp[0] - i, temp[1] - j))
						di[temp[0] - i, temp[1] - j] = di[temp] + 1
				if temp[1] + j <= n - 1:
					if (temp[0] - i, temp[1] + j) not in tried:
						q.append((temp[0] - i, temp[1] + j))
						tried.add((temp[0] - i, temp[1] + j))
						di[temp[0] - i, temp[1] + j] = di[temp] + 1
			if temp[0] + i <= n - 1:
				if temp[1] - j >= 0:
					if (temp[0] + i, temp[1] - j) not in tried:
						q.append((temp[0] + i, temp[1] - j))
						tried.add((temp[0] + i, temp[1] - j))
						di[temp[0] + i, temp[1] - j] = di[temp] + 1
				if temp[1] + j <= n - 1:
					if (temp[0] + i, temp[1] + j) not in tried:
						q.append((temp[0] + i, temp[1] + j))
						tried.add((temp[0] + i, temp[1] + j))
						di[temp[0] + i, temp[1] + j] = di[temp] + 1
			if temp[0] - j >= 0:
				if temp[1] - i >= 0:
					if (temp[0] - j, temp[1] - i) not in tried:
						q.append((temp[0] - j, temp[1] - i))
						tried.add((temp[0] - j, temp[1] - i))
						di[temp[0] - j, temp[1] - i] = di[temp] + 1
				if temp[1] + i <= n - 1:
					if (temp[0] - j, temp[1] + i) not in tried:
						q.append((temp[0] - j, temp[1] + i))
						tried.add((temp[0] - j, temp[1] + i))
						di[temp[0] - j, temp[1] + i] = di[temp] + 1
			if temp[0] + j <= n - 1:
				if temp[1] - i >= 0:
					if (temp[0] + j, temp[1] - i) not in tried:
						q.append((temp[0] + j, temp[1] - i))
						tried.add((temp[0] + j, temp[1] - i))
						di[temp[0] + j, temp[1] - i] = di[temp] + 1
				if temp[1] + i <= n - 1:
					if (temp[0] + j, temp[1] + i) not in tried:
						q.append((temp[0] + j, temp[1] + i))
						tried.add((temp[0] + j, temp[1] + i))
						di[temp[0] + j, temp[1] + i] = di[temp] + 1
			if (n - 1, n - 1) in di:
				goal = True
				curans.append(di[n - 1, n - 1])
			if len(q) == 0:
				goal = True
				curans.append(-1)
	for l in range(len(curans)):
		print(str(curans[l]) + ' ', end='')
	print('')


import sys
from collections import deque
n = int(input().strip())

def find(n, i, j):
	visited = {}
	visited[0, 0] = 0
	path = deque()
	path.append((0, 0))
	while len(path) != 0:
		cell = path.pop()
		coefs = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (-j, i), (j, -i), (-j, -i)]
		if cell[0] + i == n - 1 and cell[1] + j == n - 1 or (cell[0] + j == n - 1 and cell[1] + i == n - 1):
			return visited[cell] + 1
		for (a, b) in coefs:
			tmp = (cell[0] + a, cell[1] + b)
			if tmp[0] >= 0 and tmp[0] < n and (tmp[1] >= 0) and (tmp[1] < n) and (not tmp in visited):
				path.appendleft(tmp)
				visited[tmp] = visited[cell] + 1
	return -1
answer = []
for i in range(n - 1):
	answer.append([])
	for j in range(n - 1):
		answer[i].append(0)
for i in range(1, n):
	for j in range(i, n):
		answer[i - 1][j - 1] = find(n, i, j)
		answer[j - 1][i - 1] = answer[i - 1][j - 1]
for i in range(0, n - 1):
	for j in range(0, n - 1):
		print(answer[i][j], end=' ')
	print()


import sys

def make_act_set(a, b):
	actset = []
	actset.append([a, b])
	actset.append([-a, b])
	actset.append([a, -b])
	actset.append([-a, -b])
	actset.append([b, a])
	actset.append([-b, a])
	actset.append([b, -a])
	actset.append([-b, -a])
	return actset

def make_xy_set(N):
	xyset = []
	for x in range(N):
		for y in range(N):
			xyset.append([x, y])
	xyset.remove([0, 0])
	return xyset

def take_step(cur_xy_list, actset, xyset, N):
	new_xy_list = []
	for curxy in cur_xy_list:
		for act in actset:
			new_xy = [i for i in curxy]
			new_xy[0] += act[0]
			new_xy[1] += act[1]
			if new_xy in xyset:
				new_xy_list.append(new_xy)
				xyset.remove(new_xy)
		if not [N - 1, N - 1] in xyset:
			break
	return (new_xy_list, xyset)

def find_sol(N, index_pair):
	xyset = make_xy_set(N)
	actset = make_act_set(index_pair[0], index_pair[1])
	step = 0
	cur_xy_list = [[0, 0]]
	while 1:
		(cur_xy_list, xyset) = take_step(cur_xy_list, actset, xyset, N)
		step += 1
		if len(cur_xy_list) == 0:
			step = -1
			break
		elif not [N - 1, N - 1] in xyset:
			break
	return step
N = int(input().strip())
sol = []
for loof in range(N - 1):
	sol.append([0 for i in range(N - 1)])
for row in range(N - 1):
	for col in range(N - 1):
		if row > col:
			sol[row][col] = sol[col][row]
		else:
			sol[row][col] = find_sol(N, [row + 1, col + 1])
for i in range(N - 1):
	for j in range(N - 1):
		if j < N - 2:
			print(sol[i][j], end=' ')
		else:
			print(sol[i][j])


import sys
import queue

def valid(x, y, n, visited):
	return x >= 0 and x < n and (y >= 0) and (y < n) and (visited[x][y] == 0)
n = int(input().strip())
solution = {}
for a in range(1, n):
	for b in range(1, n):
		if (b, a) in solution:
			solution[a, b] = solution[b, a]
		else:
			visited = [[0 for _ in range(n)] for _ in range(n)]
			Q = queue.Queue()
			Q.put([0, 0, 0])
			visited[0][0] = 1
			found = False
			while not Q.empty():
				(x, y, s) = Q.get()
				if x == n - 1 and y == n - 1:
					found = True
					solution[a, b] = s
					break
				for p in range(-1, 2, 2):
					for q in range(-1, 2, 2):
						if valid(x + p * a, y + q * b, n, visited):
							Q.put([x + p * a, y + q * b, s + 1])
							visited[x + p * a][y + q * b] = 1
						if valid(x + p * b, y + q * a, n, visited):
							Q.put([x + p * b, y + q * a, s + 1])
							visited[x + p * b][y + q * a] = 1
			if not found:
				solution[a, b] = -1
for a in range(1, n):
	for b in range(1, n):
		print(solution[a, b], end=' ')
	print()


import sys
debug = False
inf = 1e+100

def minmove(n, a, b):
	if debug:
		print('init', n, a, b)
	memo = [[inf] * n for i in range(n)]

	def move(x, y, step):
		if x < 0 or x > n - 1:
			return False
		if y < 0 or y > n - 1:
			return False
		if memo[x][y] <= step:
			return False
		memo[x][y] = step
		if x == n - 1 and y == n - 1:
			if debug:
				print('memo', x, y, step)
			return True
		step += 1
		move(x + a, y + b, step)
		move(x + a, y - b, step)
		move(x - a, y + b, step)
		move(x - a, y - b, step)
		move(x + b, y + a, step)
		move(x + b, y - a, step)
		move(x - b, y + a, step)
		move(x - b, y - a, step)
	move(0, 0, 0)
	if memo[n - 1][n - 1] < inf:
		return memo[n - 1][n - 1]
	else:
		return -1
n = int(input().strip())
minmoves = [[0] * (n - 1) for i in range(n - 1)]
for a in range(1, n):
	for b in range(1, a + 1):
		i = a - 1
		j = b - 1
		minmoves[i][j] = minmove(n, a, b)
		minmoves[j][i] = minmoves[i][j]
		if debug:
			print('save', i, j, minmoves[i][j])
for i in range(n - 1):
	print(' '.join([str(s) for s in minmoves[i]]))


import sys
import queue
memo = dict()
n = int(input().strip())
memo[1, 1] = n - 1
for i in range(1, n):
	for j in range(1, n):
		if (min(i, j), max(i, j)) in memo:
			continue
		q = queue.Queue()
		q.put(((0, 0), 0, []))
		done = set()
		while True:
			if q.empty():
				memo[min(i, j), max(i, j)] = -1
				break
			(pos, nmoves, prevmoves) = q.get()
			if pos in done:
				continue
			done.add(pos)

			def move():
				(x, y) = pos
				for mx in (-1, 1):
					for my in (-1, 1):
						for r in (True, False):
							mv = (x + i * mx, y + j * my) if r else (x + j * mx, y + i * my)
							if mv == (n - 1, n - 1):
								memo[min(i, j), max(i, j)] = nmoves + 1
								return
							if mv[0] >= 0 and mv[1] >= 0 and (mv[0] < n) and (mv[1] < n) and (mv not in done):
								q.put((mv, nmoves + 1, prevmoves + [mv]))
			move()
			if (min(i, j), max(i, j)) in memo:
				break
	print(' '.join([str(memo[min(i, j), max(i, j)]) for j in range(1, n)]))


import sys

def print_ans(results):
	for row in results:
		for val in row:
			print(str(val), end=' ')
		print('')

def find_ans(n, a, b):
	steps = 0
	x = 0
	if a == b:
		while x < n - 1:
			x += a
			steps += 1
		if x != n - 1:
			steps = -1
		return steps
	else:
		y = 0
		moves = ((a, b), (b, a), (a, -b), (b, -a), (-a, -b), (-b, -a), (-a, b), (-b, a))
		present = []
		visited = [(0, 0)]
		present.append(moves[0])
		present.append(moves[1])
		steps = 1
		while len(present) != 0:
			for pos in present.copy():
				for movex in moves:
					n_pos = tuple((item1 + item2 for (item1, item2) in zip(pos, movex)))
					if n_pos[0] < 0 or n_pos[1] < 0 or n_pos[0] >= n or (n_pos[1] >= n):
						pass
					elif n_pos in present:
						continue
					elif n_pos in visited:
						continue
					elif n_pos == (n - 1, n - 1):
						return steps + 1
					else:
						visited.append(n_pos)
						present.append(n_pos)
				present.remove(pos)
			steps += 1
		steps = -1
		return steps
n = int(input().strip())
results = []
done = []
for a in range(n - 1):
	results.append([])
	for b in range(n - 1):
		if (b + 1, a + 1) in done:
			results[a].append(results[b][a])
		else:
			results[a].append(find_ans(n, a + 1, b + 1))
		done.append((a + 1, b + 1))
print_ans(results)


import sys

def min_dist(n, a, b):
	start = (0, 0)
	finish = (n - 1, n - 1)
	chessboard = dict()
	chessboard[start] = 0
	frontline = [start]
	while len(frontline):
		(row, col) = frontline.pop(0)
		next = [(row + r, col + c) for r in [-a, a] for c in [-b, b]]
		next.extend([(row + r, col + c) for r in [-b, b] for c in [-a, a]])
		next = filter(lambda pt: all((coord >= 0 and coord < n for coord in pt)), next)
		curr_step = chessboard[row, col] + 1
		for pt in next:
			if pt not in chessboard:
				chessboard[pt] = curr_step
				frontline.append(pt)
			elif chessboard[pt] > curr_step:
				chessboard[pt] = curr_step
				frontline.append(pt)
	return chessboard[finish] if finish in chessboard else -1
n = int(input().strip())
answer = [[min_dist(n, a, b) for a in range(1, n)] for b in range(1, n)]
for line in answer:
	print(*line)


import sys
n = int(input().strip())
for a in range(1, n):
	for b in range(1, n):
		min_moves = {}

		def BFSfunction():
			origin = (1, 1)
			end = (n, n)
			line = [origin]
			min_moves[origin] = 0
			while len(line):
				current = line[0]
				line.pop(0)
				if current == end:
					print(min_moves[current], end=' ')
					return
				for move in [(a, b), (b, a), (-a, -b), (-b, -a), (a, -b), (-a, b), (-b, a), (b, -a)]:
					plus = (current[0] + move[0], current[1] + move[1])
					if plus[0] > end[0] or plus[1] > end[1] or plus[0] < 1 or (plus[1] < 1):
						continue
					if plus not in min_moves:
						min_moves[plus] = min_moves[current] + 1
						line.append(plus)
			else:
				print(-1, end=' ')
		BFSfunction()
	print()


import sys

def min_path(n, a, b):
	m = []
	processed = []
	for i in range(n):
		m.append([-1] * n)
		processed.append([False] * n)
	m[0][0] = 0
	while True:
		mn = -1
		mni = -1
		mnj = -1
		for i in range(n):
			for j in range(n):
				if m[i][j] != -1 and (not processed[i][j]):
					if mn == -1 or m[i][j] < mn:
						mn = m[i][j]
						mni = i
						mnj = j
		if mni == -1 and mnj == -1:
			break
		dirs = [[1, 1], [1, -1], [-1, 1], [-1, -1]]
		for d in dirs:
			ii = mni + d[0] * a
			jj = mnj + d[1] * b
			if ii >= 0 and ii < n and (jj >= 0) and (jj < n):
				if m[ii][jj] == -1:
					m[ii][jj] = mn + 1
				else:
					m[ii][jj] = min(mn + 1, m[ii][jj])
			ii = mni + d[0] * b
			jj = mnj + d[1] * a
			if ii >= 0 and ii < n and (jj >= 0) and (jj < n):
				if m[ii][jj] == -1:
					m[ii][jj] = mn + 1
				else:
					m[ii][jj] = min(mn + 1, m[ii][jj])
		processed[mni][mnj] = True
		if mni == n - 1 and mnj == n - 1:
			break
	return m[n - 1][n - 1]
N = int(input())
for i in range(1, N):
	for j in range(1, N):
		print(min_path(N, i, j), end=' ')
	print()


import sys
n = int(input().strip())
board = []
for i in range(n):
	for j in range(n):
		board.append([i, j])
zero = [0, 0]
reached = [[n - 1, n - 1]]
for i in range(1, n):
	ans = []
	for j in range(1, n):
		reached = [[n - 1, n - 1]]
		reachable = []
		moves = [[i, j], [i, -j], [-i, j], [-i, -j], [j, i], [j, -i], [-j, i], [-j, -i]]
		for square in reached:
			for move in moves:
				newsquare = [square[0] + move[0], square[1] + move[1]]
				if newsquare in board:
					reachable.append(newsquare)
		movecount = 1
		while zero not in reachable and len(reachable) > 0 and (movecount < 100):
			newreachable = []
			for square in reachable:
				for move in moves:
					newsquare = [square[0] + move[0], square[1] + move[1]]
					if newsquare in board:
						if newsquare not in newreachable:
							newreachable.append(newsquare)
			for x in reached:
				if x in newreachable:
					newreachable.remove(x)
			for x in newreachable:
				reached.append(x)
			reachable = newreachable.copy()
			movecount += 1
		if zero in reachable:
			ans.append(movecount)
		if len(reachable) == 0:
			ans.append(-1)
	for x in ans:
		print(x, end=' ')
	print()


import sys

def inBoardAndNotVisited(x, y, knight_visited, n):
	result = False
	if x >= 0 and y >= 0 and (x < n) and (y < n) and (not knight_visited[x][y]):
		result = True
	return result

def knightNewReached(x_ini, y_ini, x_goal, y_goal, jump, knight_visited, next_pos, knight_new_reach, n):
	for i in range(8):
		x_n = x_ini + next_pos[i][0]
		y_n = y_ini + next_pos[i][1]
		if inBoardAndNotVisited(x_n, y_n, knight_visited, n):
			knight_visited[x_n][y_n] = True
			knight_new_reach.add((x_n, y_n))

def knightl(a, b, x_goal, y_goal, n):
	jump = 0
	next_pos = [[a, b], [a, -b], [-a, b], [-a, -b], [b, a], [b, -a], [-b, a], [-b, -a]]
	x_ini = 0
	y_ini = 0
	knight_visited = [[False for j in range(n)] for i in range(n)]
	knight_visited[x_ini][y_ini] = True
	knight_reach = {(x_ini, y_ini)}
	reached = False
	while not reached and len(knight_reach) > 0:
		knight_new_reach = set()
		for i in knight_reach:
			x_ini = i[0]
			y_ini = i[1]
			knightNewReached(x_ini, y_ini, x_goal, y_goal, jump, knight_visited, next_pos, knight_new_reach, n)
		knight_reach = knight_new_reach
		jump += 1
		if (x_goal, y_goal) in knight_reach:
			reached = True
	if not reached:
		jump = -1
	return jump
n = int(input().strip())
paths = []
knight_taken = [[False for j in range(n)] for i in range(n)]
knight_value = [[0 for j in range(n)] for i in range(n)]
for a in range(1, n, 1):
	line = []
	for b in range(1, n, 1):
		if not knight_taken[a][b]:
			jump = knightl(a, b, n - 1, n - 1, n)
			knight_taken[a][b] = True
			knight_taken[b][a] = True
			knight_value[a][b] = jump
			knight_value[b][a] = jump
		line.append(knight_value[a][b])
	paths.append(line)
for line in paths:
	print(line[0], end='')
	for i in range(1, len(line), 1):
		print('', line[i], end='')
	print('')


import sys
from collections import deque
n = int(input().strip())

def bfs(n, a, b):
	front = set()
	que = deque()
	que.append((1, 1, 0))
	front.add((1, 1))
	while len(que) != 0:
		(cur_i, cur_j, step) = que.popleft()
		if cur_i == n and cur_j == n:
			return step
		directions = [(a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)]
		for dir in directions:
			(new_i, new_j) = (cur_i + dir[0], cur_j + dir[1])
			if new_i >= 1 and new_i <= n and (new_j >= 1) and (new_j <= n) and ((new_i, new_j) not in front):
				que.append((new_i, new_j, step + 1))
				front.add((new_i, new_j))
	return -1
for i in range(1, n):
	for j in range(1, n):
		print(bfs(n, i, j), end=' ')
	print()


import sys

def calc_coords(current, movement, n):
	coords = []
	coords.append((current[0] + movement[0], current[1] + movement[1]))
	coords.append((current[0] + movement[0], current[1] - movement[1]))
	coords.append((current[0] - movement[0], current[1] + movement[1]))
	coords.append((current[0] - movement[0], current[1] - movement[1]))
	coords.append((current[0] + movement[1], current[1] + movement[0]))
	coords.append((current[0] + movement[1], current[1] - movement[0]))
	coords.append((current[0] - movement[1], current[1] + movement[0]))
	coords.append((current[0] - movement[1], current[1] - movement[0]))
	copy = coords[:]
	for i in coords:
		if i[0] not in range(n) or i[1] not in range(n):
			copy.remove(i)
	return copy

def knightL(i, j, n):
	seen = set()
	queue = []
	steps = 0
	movement = (i, j)
	next_nodes = 0
	current_nodes = 1
	seen.add((0, 0))
	queue.append((0, 0))
	while queue:
		current = queue.pop(0)
		current_nodes -= 1
		if current[0] == n - 1 and current[1] == n - 1:
			return steps
		next_coords = calc_coords(current, movement, n)
		for coords in next_coords:
			if coords not in seen:
				seen.add(coords)
				queue.append(coords)
				next_nodes += 1
		if current_nodes <= 0:
			(current_nodes, next_nodes) = (next_nodes, current_nodes)
			steps += 1
	return -1
n = int(input().strip())
for i in range(1, n):
	j = 1
	while j < n:
		print(knightL(i, j, n), end=' ')
		j += 1
	print()


def way_finder(a, b, register, position):
	global count
	newpositions = [position]
	count = 0
	while 1:
		result = 0
		count += 1
		for j in range(len(newpositions)):
			i = 0
			if newpositions[i][0] - b >= 0 and newpositions[i][1] - a >= 0:
				newposition = [newpositions[i][0] - b, newpositions[i][1] - a]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] - b, newpositions[i][1] - a])
			if newpositions[i][0] - a >= 0 and newpositions[i][1] - b >= 0:
				newposition = [newpositions[i][0] - a, newpositions[i][1] - b]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] - a, newpositions[i][1] - b])
			if newpositions[i][0] - a >= 0 and newpositions[i][1] + b < n:
				newposition = [newpositions[i][0] - a, newpositions[i][1] + b]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] - a, newpositions[i][1] + b])
			if newpositions[i][0] + a < n and newpositions[i][1] - b >= 0:
				newposition = [newpositions[i][0] + a, newpositions[i][1] - b]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] + a, newpositions[i][1] - b])
			if newpositions[i][0] - b >= 0 and newpositions[i][1] + a < n:
				newposition = [newpositions[i][0] - b, newpositions[i][1] + a]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] - b, newpositions[i][1] + a])
			if newpositions[i][0] + b < n and newpositions[i][1] - a >= 0:
				newposition = [newpositions[i][0] + b, newpositions[i][1] - a]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] + b, newpositions[i][1] - a])
			if newpositions[i][0] + a < n and newpositions[i][1] + b < n:
				newposition = [newpositions[i][0] + a, newpositions[i][1] + b]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] + a, newpositions[i][1] + b])
			if newpositions[i][0] + b < n and newpositions[i][1] + a < n:
				newposition = [newpositions[i][0] + b, newpositions[i][1] + a]
				if newposition == [0, 0]:
					result = 2
					break
				if newposition not in register and newposition not in newpositions:
					result = 1
					newpositions.append([newpositions[i][0] + b, newpositions[i][1] + a])
			newpositions.pop(0)
		register = register + newpositions
		if result == 0:
			return -1
		if result == 2:
			return count
n = int(input())
resultmatrix = [[[] for x in range(n - 1)] for x in range(n - 1)]
for i in range(1, n):
	for j in range(1, n):
		count = 0
		position = [n - 1, n - 1]
		resultmatrix[i - 1][j - 1] = way_finder(i, j, [[n - 1, n - 1]], position)
for i in range(0, n - 1):
	print(' '.join(map(str, resultmatrix[i])))


import collections
n = int(input().strip())
GOAL = (n - 1, n - 1)

def get_neighbors(square, a, b):
	diffs = set([(a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)])
	for d in diffs:
		neighbor = (square[0] + d[0], square[1] + d[1])
		if 0 <= neighbor[0] < n and 0 <= neighbor[1] < n:
			yield neighbor

def moves_to_goal(a, b):
	closed_squares = set([(0, 0)])
	frontier_squares = collections.deque([((0, 0), 0)])
	while len(frontier_squares):
		(current_square, path_len) = frontier_squares.popleft()
		neighbors = get_neighbors(current_square, a, b)
		for neighbor in neighbors:
			if neighbor == GOAL:
				return path_len + 1
			if neighbor not in closed_squares:
				closed_squares.add(neighbor)
				frontier_squares.append((neighbor, path_len + 1))
	return -1
for a in range(1, n):
	row = []
	for b in range(1, n):
		row.append(str(moves_to_goal(a, b)))
	print(' '.join(row))


import sys
n = int(input().strip())
m = [[-1 for x in range(n)] for y in range(n)]
g = 1
while g <= n - 1:
	d = 1
	while d <= n - 1:
		visited = []
		visited.append((n - 1, n - 1))
		counter = 0
		cur_len = 0
		diff = len(visited) - cur_len
		if m[g][d] == -1:
			while len(visited) > cur_len and (0, 0) not in visited:
				cur_len = len(visited)
				arr = visited[len(visited) - diff:len(visited)]
				h = 0
				while h <= len(arr) - 1:
					(t, r) = arr[h]
					if (t - g <= n - 1 and t - g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t - g, r - d) not in visited):
						visited.append((t - g, r - d))
					if (t - g <= n - 1 and t - g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t - g, r + d) not in visited):
						visited.append((t - g, r + d))
					if (t + g <= n - 1 and t + g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t + g, r - d) not in visited):
						visited.append((t + g, r - d))
					if (t + g <= n - 1 and t + g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t + g, r + d) not in visited):
						visited.append((t + g, r + d))
					if (t - d <= n - 1 and t - d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t - d, r - g) not in visited):
						visited.append((t - d, r - g))
					if (t - d <= n - 1 and t - d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t - d, r + g) not in visited):
						visited.append((t - d, r + g))
					if (t + d <= n - 1 and t + d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t + d, r - g) not in visited):
						visited.append((t + d, r - g))
					if (t + d <= n - 1 and t + d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t + d, r + g) not in visited):
						visited.append((t + d, r + g))
					h = h + 1
				diff = len(visited) - cur_len
				counter = counter + 1
			if (0, 0) in visited:
				m[g][d] = counter
				m[d][g] = m[g][d]
		d = d + 1
	g = g + 1
p = 1
while p <= n - 1:
	line = ''
	g = 1
	while g <= n - 1:
		line = line + ' ' + str(m[p][g])
		g = g + 1
	print(line.lstrip())
	p = p + 1


import sys
n = int(input().strip())
for a in range(1, n):
	for b in range(1, n):
		min_moves = {}

		def BFSfunction():
			origin = (1, 1)
			end = (n, n)
			line = [origin]
			min_moves[origin] = 0
			while len(line):
				current = line[0]
				line.pop(0)
				if current == end:
					print(min_moves[current], end=' ')
					return
				for move in [(a, b), (b, a), (-a, -b), (-b, -a), (a, -b), (-a, b), (-b, a), (b, -a)]:
					plus = (current[0] + move[0], current[1] + move[1])
					if plus[0] > end[0] or plus[1] > end[1] or plus[0] < 1 or (plus[1] < 1):
						continue
					if plus not in min_moves:
						min_moves[plus] = min_moves[current] + 1
						line.append(plus)
			else:
				print(-1, end=' ')
		BFSfunction()
	print()


import sys
n = int(input().strip())
A = []
for a in range(1, n):
	B = []
	for b in range(1, n):
		P = {(0, 0)}
		c = 0
		f = True
		V = set()
		while f:
			c += 1
			Q = set()
			V = V | P
			for p in P:
				if (p[0] == n - 1) & (p[1] == n - 1):
					f = False
					break
				if (0 <= p[0] + a < n) & (0 <= p[1] + b < n):
					Q.add((p[0] + a, p[1] + b))
				if (0 <= p[0] - a < n) & (0 <= p[1] - b < n):
					Q.add((p[0] - a, p[1] - b))
				if (0 <= p[0] - a < n) & (0 <= p[1] + b < n):
					Q.add((p[0] - a, p[1] + b))
				if (0 <= p[0] + a < n) & (0 <= p[1] - b < n):
					Q.add((p[0] + a, p[1] - b))
				if (0 <= p[0] + b < n) & (0 <= p[1] + a < n):
					Q.add((p[0] + b, p[1] + a))
				if (0 <= p[0] - b < n) & (0 <= p[1] - a < n):
					Q.add((p[0] - b, p[1] - a))
				if (0 <= p[0] - b < n) & (0 <= p[1] + a < n):
					Q.add((p[0] - b, p[1] + a))
				if (0 <= p[0] + b < n) & (0 <= p[1] - a < n):
					Q.add((p[0] + b, p[1] - a))
			P = set()
			P = P | Q
			P = P - V
			if len(P) == 0:
				break
		if not f:
			B.append(c - 1)
		else:
			B.append(-1)
	A.append(B)
for a in A:
	for b in a:
		print(b, end=' ')
	print('')


from collections import deque
n = int(input())

def is_square(a):
	return a[0] >= 0 and a[1] >= 0 and (a[0] < n) and (a[1] < n)

def getDist(dx, dy):
	dist = {}
	que = deque()
	que.append((0, 0, 0))
	direc = [(dx, dy), (dy, dx), (-dx, dy), (-dy, dx), (-dx, -dy), (-dy, -dx), (dx, -dy), (dy, -dx)]
	while len(que) > 0:
		(a0, a1, d) = que.popleft()
		a = (a0, a1)
		if not is_square(a) or (a in dist and d >= dist[a]):
			continue
		dist[a] = d
		for dire in direc:
			que.append((a[0] + dire[0], a[1] + dire[1], d + 1))
	if (n - 1, n - 1) in dist:
		return dist[n - 1, n - 1]
	else:
		return -1
for dx in range(1, n):
	out = []
	for dy in range(1, n):
		out.append(getDist(dx, dy))
	print(*out)


from collections import deque
from itertools import product, permutations

def deltas(y, x):
	perms = permutations([y, x])
	mul = product((1, -1), repeat=2)
	return ((p[0] * m[0], p[1] * m[1]) for (p, m) in product(perms, mul))
n = int(input())
res = [[None] * (n - 1) for _ in range(n - 1)]
for i in range(1, n):
	for j in range(i, n):
		dp = [[-1] * n for _ in range(n)]
		que = deque(((0, 0),))
		dp[0][0] = 0
		while que:
			(y, x) = que.popleft()
			for (dy, dx) in deltas(i, j):
				y1 = y + dy
				x1 = x + dx
				if 0 <= y1 < n and 0 <= x1 < n and (dp[y1][x1] == -1):
					dp[y1][x1] = dp[y][x] + 1
					que.append((y1, x1))
		res[i - 1][j - 1] = dp[-1][-1]
		res[j - 1][i - 1] = dp[-1][-1]
print(*(' '.join((str(x) for x in row)) for row in res), sep='\n')


import sys
from collections import deque
import ast

def build_graph(graph, start, end, movement, n):
	queue = deque([start])
	visited = {start: False}
	count = 0
	while queue:
		u = queue[0]
		queue.remove(u)
		if not visited.get(u, False):
			count += 1
			visited[u] = True
			fill_neighbours(graph, u, movement, n)
			neighbours = graph.get(u)
			for v in neighbours:
				if not visited.get(v, False):
					queue.append(v)

def add_neighbour(graph, node, neighbours):
	for n in neighbours:
		if n not in graph.get(node, []):
			graph.get(node).append(neighbours)

def fill_neighbours(graph, node, movement, n):
	a = movement[0]
	b = movement[1]
	pos = ast.literal_eval(node)
	x = pos[0]
	y = pos[1]
	legal_pos = deque()
	for i in [x + a, x - a]:
		for j in [y - b, y + b]:
			if 0 <= i < n and 0 <= j < n:
				legal_pos.append((i, j))
	for i in [x + b, x - b]:
		for j in [y - a, y + a]:
			if 0 <= i < n and 0 <= j < n:
				legal_pos.append((i, j))
	for pos in legal_pos:
		if str(pos) in graph:
			neighbours = graph.get(str(pos))
		else:
			graph[str(pos)] = []
		add_neighbour(graph, node, str(pos))

def BFS(graph, source_id, target_id):
	Q = deque([source_id])
	distance = {source_id: 0}
	previous = {}
	Flag = {source_id: True}
	while Q:
		u = Q[0]
		Q.remove(u)
		for v in graph.get(u):
			if Flag.get(v) is not True:
				distance[v] = distance[u] + 1
				previous[v] = u
				Flag[v] = True
				Q.append(v)
	return (previous, distance)

def main():
	mode = int(input().strip())
	for i in range(1, mode):
		line = []
		for j in range(1, mode):
			start = str((0, 0))
			end = str((mode - 1, mode - 1))
			graph = {start: [], end: []}
			build_graph(graph, start, end, (i, j), mode)
			(previous, distance) = BFS(graph, start, end)
			d = distance.get(end, -1)
			line.append(d)
		print(*line)
main()


from operator import __add__, __sub__
functions = [(f, g) for f in [__add__, __sub__] for g in [__add__, __sub__]]

def positions(i, j, a, b):
	return [(f(i, x), g(j, k)) for (x, k) in [(a, b), (b, a)] for (f, g) in functions]

def onmap(i, j, n):
	_o = lambda i, n: i < n and i >= 0
	return _o(i, n) and _o(j, n)

def f(i, j, a, b, n, T, D, P):
	p = positions(i, j, a, b)
	for (i, j) in p:
		if onmap(i, j, n):
			if T[i, j] == -1:
				T[i, j] = D
				P.append((i, j, D + 1))
	if len(P) > 0:
		(i, j, D) = P.pop(0)
		f(i, j, a, b, n, T, D, P)
n = int(input())
K = {(i, j): -1 for i in range(n) for j in range(n)}
for X in range(1, n):
	for Y in range(1, n):
		T = {(i, j): -1 for i in range(n) for j in range(n)}
		T[n - 1, n - 1] = 0
		f(n - 1, n - 1, X, Y, n, T, 1, list())
		K[X, Y] = T[0, 0]
for X in range(1, n):
	for Y in range(1, n):
		print(K[X, Y], end=' ')
	print()


import sys
n = int(input().strip())

def isOk(i, j):
	if i >= 0 and i < n and (j >= 0) and (j < n):
		return True
	else:
		return False

def bfs(i, j, a, b, res):
	queue = []
	temp = (i, j)
	queue.append(temp)
	visited[i][j] = True
	res[i][j] = 0
	dist = 0
	x = [a, a, -a, -a, b, b, -b, -b]
	y = [b, -b, b, -b, a, -a, a, -a]
	while len(queue) != 0:
		temp = queue.pop(0)
		for w in range(len(x)):
			if isOk(temp[0] + x[w], temp[1] + y[w]) and (not visited[temp[0] + x[w]][temp[1] + y[w]]):
				res[temp[0] + x[w]][temp[1] + y[w]] = res[temp[0]][temp[1]] + 1
				visited[temp[0] + x[w]][temp[1] + y[w]] = True
				temp2 = (temp[0] + x[w], temp[1] + y[w])
				queue.append(temp2)
	return res[n - 1][n - 1]
result = [[-1] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		visited = [[False] * n for _ in range(n)]
		res = [[-1] * n for _ in range(n)]
		temp = bfs(0, 0, i, j, res)
		result[i][j] = temp
for i in range(1, n):
	for j in range(1, n):
		print(result[i][j], end=' ')
	print('')


import sys
from collections import deque
n = int(input().strip())
for i in range(1, n):
	for j in range(1, n):
		flag = 0
		dq = deque()
		dq.append((0, 0, 0))
		vstd = dict()

		def is_valid(x2, y2):
			if x2 >= 0 and y2 >= 0 and (x2 < n) and (y2 < n):
				return 1
			return 0
		while len(dq):
			(x, y, moves) = dq.popleft()
			if vstd.get((x, y)):
				continue
			vstd[x, y] = 1
			if (x, y) == (n - 1, n - 1):
				print(moves, end=' ')
				flag = 1
				break
			for dx in (i, -i):
				for dy in (j, -j):
					if is_valid(x + dx, y + dy):
						dq.append((x + dx, y + dy, moves + 1))
			for dx in (j, -j):
				for dy in (i, -i):
					if is_valid(x + dx, y + dy):
						dq.append((x + dx, y + dy, moves + 1))
		if not flag:
			print(-1, end=' ')
	print()


from collections import deque

def next_move(i, j, a, b, n):
	move1 = [(i + d1, j + d2) for d1 in (-a, a) for d2 in (-b, b)]
	move2 = [(i + d1, j + d2) for d1 in (-b, b) for d2 in (-a, a)]
	return filter(lambda t: all(map(lambda x: 0 <= x < n, t)), move1 + move2)

def knightl(a, b, n):
	visited = [[False for _ in range(n)] for _ in range(n)]
	visited[0][0] = True
	q = deque([(0, 0, 0)])
	while q:
		(old_x, old_y, c) = q.popleft()
		for newpos in next_move(old_x, old_y, a, b, n):
			(x, y) = newpos
			if not visited[x][y]:
				if (x, y) == (n - 1, n - 1):
					return c + 1
				visited[x][y] = True
				q.append((x, y, c + 1))
	return -1
n = int(input().strip())
for a in range(1, n):
	line = []
	for b in range(1, n):
		line.append(knightl(a, b, n))
	print(*line)


import collections
n = int(input())
result = [[-1] * (n - 1) for i in range(n - 1)]
for a in range(1, n + 1):
	for b in range(1, n + 1):
		moves = [(-a, -b), (-a, b), (a, -b), (a, b), (-b, -a), (-b, a), (b, -a), (b, a)]
		visited = [[False] * n for i in range(n)]
		q = collections.deque([((0, 0), 0)])
		visited[0][0] = True
		while q:
			(x, steps) = q.popleft()
			visited[x[0]][x[1]] = True
			if x == (n - 1, n - 1):
				result[a - 1][b - 1] = steps
				break
			for move in moves:
				target = (x[0] + move[0], x[1] + move[1])
				if 0 <= target[0] < n and 0 <= target[1] < n and (not visited[target[0]][target[1]]):
					q.append((target, steps + 1))
					visited[target[0]][target[1]] = True
for row in result:
	print(*row)


import sys
from collections import deque

def check_v(n, sol, c, x, y):
	if x >= 0 and x < n and (y >= 0) and (y < n):
		if sol[x][y] == -1:
			sol[x][y] = c + 1
			return [c + 1, x, y]

def dfs(n, a, b):
	sol = [[-1 for _ in range(n)] for _ in range(n)]
	sol[0][0] = 0
	q = deque()
	q.append([0, 0, 0])
	while len(q) > 0:
		(c, x, y) = q.popleft()
		nodes = list()
		nodes.append(check_v(n, sol, c, x + a, y + b))
		nodes.append(check_v(n, sol, c, x + a, y - b))
		nodes.append(check_v(n, sol, c, x - a, y + b))
		nodes.append(check_v(n, sol, c, x - a, y - b))
		nodes.append(check_v(n, sol, c, x + b, y + a))
		nodes.append(check_v(n, sol, c, x + b, y - a))
		nodes.append(check_v(n, sol, c, x - b, y + a))
		nodes.append(check_v(n, sol, c, x - b, y - a))
		for node in nodes:
			if node != None:
				q.append(node)
	return sol[n - 1][n - 1]
n = int(input().strip())
sol = list()
for i in range(1, n):
	l = list()
	sol.append(l)
	for j in range(1, n):
		l.append(dfs(n, i, j))
for l in sol:
	print(' '.join([str(i) for i in l]))


import sys
n = int(input().strip())
times = [-1, 1]

def shortest(n, i, j):
	dist = [[sys.maxsize for _ in range(n)] for _ in range(n)]
	dist[0][0] = 0
	queue = [(0, 0)]
	while queue and dist[n - 1][n - 1] == sys.maxsize:
		(x, y) = queue.pop(0)
		cnt = dist[x][y]
		for i1 in times:
			for i2 in times:
				nx = x + i1 * i
				ny = y + i2 * j
				if nx < n and nx >= 0 and (ny < n) and (ny >= 0):
					if dist[nx][ny] > cnt + 1:
						dist[nx][ny] = cnt + 1
						queue.append((nx, ny))
				nx = x + i1 * j
				ny = y + i2 * i
				if nx < n and nx >= 0 and (ny < n) and (ny >= 0):
					if dist[nx][ny] > cnt + 1:
						dist[nx][ny] = cnt + 1
						queue.append((nx, ny))
	return dist[n - 1][n - 1]
for i in range(1, n):
	for j in range(1, n):
		rslt = shortest(n, i, j)
		if rslt == sys.maxsize:
			print('-1', end=' ')
		else:
			print(rslt, end=' ')
	print('')


import sys
n = int(input().strip())
for i in range(1, n):
	mvs = []
	for j in range(1, n):
		v = set([])
		q = [(0, 0)]
		ql = [0]
		while q:
			x = q.pop(0)
			lv = ql.pop(0)
			if x == (n - 1, n - 1):
				mvs.append(lv)
				break
			if x in v:
				continue
			v.add(x)
			l = [y for y in [(x[0] + j, x[1] + i), (x[0] + i, x[1] + j), (x[0] + j, x[1] - i), (x[0] + i, x[1] - j), (x[0] - j, x[1] - i), (x[0] - i, x[1] - j), (x[0] - j, x[1] + i), (x[0] - i, x[1] + j)] if y[0] >= 0 and y[0] < n and (y[1] >= 0) and (y[1] < n)]
			q.extend(l)
			ql.extend([lv + 1 for _ in l])
		if not q:
			mvs.append(-1)
	print(' '.join([str(x) for x in mvs]))


import sys

def all_moves(n, p, l):
	(a, b) = l
	(x, y) = p
	if x - a >= 0 and y - b >= 0:
		yield (x - a, y - b)
	if x - a >= 0 and y + b <= n:
		yield (x - a, y + b)
	if y - a >= 0 and x - b >= 0:
		yield (x - b, y - a)
	if y - a >= 0 and x + b <= n:
		yield (x + b, y - a)
	if x + a <= n and y - b >= 0:
		yield (x + a, y - b)
	if x + a <= n and y + b <= n:
		yield (x + a, y + b)
	if y + a <= n and x - b >= 0:
		yield (x - b, y + a)
	if y + a <= n and x + b <= n:
		yield (x + b, y + a)

def play(N, l):
	G = {(0, 0): {'visited': False, 'distance': 0, 'prev': None}, (N, N): {'visited': False, 'distance': float('inf'), 'prev': None}}
	p = (0, 0)
	while True:
		c = G[p]
		for neighbor in all_moves(N, p, l):
			if neighbor not in G:
				G[neighbor] = {'visited': False, 'distance': float('inf'), 'prev': None}
			n = G[neighbor]
			if not n['visited']:
				new_distance = c['distance'] + 1
				if new_distance < n['distance']:
					n['distance'] = new_distance
					n['prev'] = p
		c['visited'] = True
		if p == (N, N):
			break
		p = sorted(filter(lambda l: not l[1]['visited'], G.items()), key=lambda l: l[1]['distance'])[0][0]
		if G[p] == float('inf'):
			return -1
	p = (N, N)
	if G[p]['prev'] is None:
		return -1
	sum = 0
	while True:
		sum += 1
		p = G[p]['prev']
		if p == (0, 0):
			break
	return sum
n = int(input().strip())
for a in range(1, n):
	ans = []
	for b in range(1, n):
		ans.append(play(n - 1, (a, b)))
	print(' '.join(map(str, ans)))


from queue import Queue

def getNumMovesForKnight(i, j, n):
	s = set()
	q = Queue()
	root = (0, 0, 0)
	s.add(root)
	q.put(root)
	moves = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (-j, i), (j, -i), (-j, -i)]
	while not q.empty():
		c = q.get()
		if c[0] == n - 1 and c[1] == n - 1:
			return str(c[2])
		for move in moves:
			x = c[0] + move[0]
			y = c[1] + move[1]
			if x >= 0 and x < n and (y >= 0) and (y < n) and ((x, y) not in s):
				s.add((x, y))
				q.put((x, y, c[2] + 1))
	return '-1'
n = int(input().strip())
for i in range(1, n):
	numMoves = []
	for j in range(1, n):
		numMoves.append(getNumMovesForKnight(i, j, n))
	print(' '.join(numMoves))


class GridBfsGraph:

	def __init__(self, n, neighbours):
		self.visited = {}
		self.n = n
		self.neighbours = neighbours

	def is_node_valid(self, node):
		if 0 <= node[0] and node[0] < self.n and (0 <= node[1]) and (node[1] < self.n):
			return True
		return False

	def get_neighbours(self, node):
		next_nodes = [(node[0] + dr, node[1] + dc) for (dr, dc) in self.neighbours]
		return [node for node in next_nodes if self.is_node_valid(node)]

	def breadth_first_search(self, starting_node):
		from collections import deque
		queue = deque([])
		queue.append((starting_node, 0))
		while len(queue) > 0:
			(current_node, steps) = queue.popleft()
			if not self.is_node_valid(current_node):
				continue
			if current_node[0] == self.n - 1 and current_node[1] == self.n - 1:
				return steps
			if current_node in self.visited:
				continue
			self.visited[current_node] = True
			for next_node in self.get_neighbours(current_node):
				queue.append((next_node, steps + 1))
		return -1
n = int(input())
for i in range(1, n):
	for j in range(1, n):
		graph = GridBfsGraph(n, [(-i, j), (-i, -j), (i, j), (i, -j), (j, i), (j, -i), (-j, i), (-j, -i)])
		print(graph.breadth_first_search((0, 0)), end=' ')
	print()


def bfs(x, y, target_x, target_y, movements):
	stack = list()
	stack.append((x, y, 0))
	to_visit = set()
	if x == target_x and y == target_y:
		return 0
	else:
		i = 0
		while len(stack) > 0:
			(x, y, depth) = stack.pop(0)
			for (dx, dy) in movements:
				px = x + dx
				py = y + dy
				if px == target_x and py == target_y:
					return depth + 1
				elif (0 <= px < N and 0 <= py < N) and (not (px, py) in to_visit):
					stack.append((px, py, depth + 1))
					to_visit.add((px, py))
			i += 1
	return -1
N = int(input())
for i in range(1, N):
	for j in range(1, N):
		cache = dict()
		movements = [(i, j), (i, -j), (-i, -j), (-i, j), (j, i), (j, -i), (-j, -i), (-j, i)]
		distance = bfs(0, 0, N - 1, N - 1, movements)
		print(distance, end=' ')
	print('')


from collections import deque

def dfs(i, j):
	board = tuple(([-1] * n for _ in range(n)))
	board[0][0] = 0
	cache = deque(((0, 0),))
	while cache:
		(x, y) = cache.popleft()
		steps = board[x][y] + 1
		for (a, b) in ((x + i, y + j), (x + i, y - j), (x - i, y + j), (x - i, y - j), (x + j, y + i), (x + j, y - i), (x - j, y + i), (x - j, y - i)):
			if 0 <= a < n and 0 <= b < n and (board[a][b] == -1):
				cache.append((a, b))
				board[a][b] = steps
	return str(board[-1][-1])
n = int(input().strip())
nm1 = n - 1
result = tuple(([None] * nm1 for _ in range(nm1)))
for i in range(nm1):
	for j in range(i, nm1):
		result[i][j] = result[j][i] = dfs(i + 1, j + 1)
print('\n'.join((' '.join(row) for row in result)))


import sys
from collections import deque
n = int(input().strip())

def moves(visited, x, y, a, b):
	temp = {(x + a, y + b), (x + a, y - b), (x - a, y + b), (x - a, y - b), (x + b, y + a), (x + b, y - a), (x - b, y + a), (x - b, y - a)}
	final = set()
	for val in temp:
		if -1 < val[0] < n and -1 < val[1] < n and (visited[val[0]][val[1]] == 0):
			final.add(val)
	return final
for a in range(1, n):
	for b in range(1, n):
		queue = deque()
		queue.append((0, 0))
		childqueue = set()
		count = 0
		visited = [[0 for j in range(n)] for i in range(n)]
		while queue or childqueue:
			current = queue.popleft()
			visited[current[0]][current[1]] = 1
			temp = moves(visited, *current + (a, b))
			if (n - 1, n - 1) in temp:
				print(count + 1, end=' ')
				break
			childqueue = childqueue.union(temp)
			if not queue:
				queue = deque(childqueue)
				count += 1
				childqueue = set()
		else:
			print('-1', end=' ')
	print('')


import sys

def check(x, y, n, b, p):
	if x >= 0 and x < n and (y >= 0) and (y < n) and (b[x][y] == -1 or b[x][y] > p):
		return True
	return False
n = int(input().strip())
res = [[-1] * n for k in range(n)]
for i in range(1, n, 1):
	res = []
	for j in range(1, n, 1):
		q = [[0, 0, 0]]
		b = [[-1] * n for k in range(n)]
		b[0][0] = 0
		while q:
			new_q = []
			for k in range(len(q)):
				p = q[k]
				if check(p[0] + i, p[1] + j, n, b, p[2] + 1) == True:
					b[p[0] + i][p[1] + j] = p[2] + 1
					new_q.append([p[0] + i, p[1] + j, p[2] + 1])
				if check(p[0] + j, p[1] + i, n, b, p[2] + 1) == True:
					b[p[0] + j][p[1] + i] = p[2] + 1
					new_q.append([p[0] + j, p[1] + i, p[2] + 1])
				if check(p[0] - i, p[1] + j, n, b, p[2] + 1) == True:
					b[p[0] - i][p[1] + j] = p[2] + 1
					new_q.append([p[0] - i, p[1] + j, p[2] + 1])
				if check(p[0] - j, p[1] + i, n, b, p[2] + 1) == True:
					b[p[0] - j][p[1] + i] = p[2] + 1
					new_q.append([p[0] - j, p[1] + i, p[2] + 1])
				if check(p[0] - i, p[1] - j, n, b, p[2] + 1) == True:
					b[p[0] - i][p[1] - j] = p[2] + 1
					new_q.append([p[0] - i, p[1] - j, p[2] + 1])
				if check(p[0] - j, p[1] - i, n, b, p[2] + 1) == True:
					b[p[0] - j][p[1] - i] = p[2] + 1
					new_q.append([p[0] - j, p[1] - i, p[2] + 1])
				if check(p[0] + i, p[1] - j, n, b, p[2] + 1) == True:
					b[p[0] + i][p[1] - j] = p[2] + 1
					new_q.append([p[0] + i, p[1] - j, p[2] + 1])
				if check(p[0] + j, p[1] - i, n, b, p[2] + 1) == True:
					b[p[0] + j][p[1] - i] = p[2] + 1
					new_q.append([p[0] + j, p[1] - i, p[2] + 1])
			q = new_q
		res.append(b[n - 1][n - 1])
	print(' '.join(('{0}'.format(r) for r in res)))


import sys

def compute(N, a, b):
	pMap = {(0, 0): 0}
	newPositions = [(0, 0)]
	target = (N - 1, N - 1)
	while len(newPositions):
		(px, py) = newPositions.pop(0)
		dests = [(px + a, py + b), (px + a, py - b), (px - a, py + b), (px - a, py - b), (px + b, py + a), (px + b, py - a), (px - b, py + a), (px - b, py - a)]
		for d in dests:
			if d not in pMap and 0 <= d[0] < N and (0 <= d[1] < N):
				moves = pMap[px, py] + 1
				if d == target:
					return moves
				pMap[d] = moves
				newPositions.append(d)
	return -1
N = int(input().strip())
for i in range(1, N):
	rowVals = []
	for j in range(1, N):
		rowVals.append(compute(N, i, j))
	print(' '.join((str(x) for x in rowVals)))


import sys
import queue

class state:

	def __init__(self, x, y, num_moves):
		(self.x, self.y, self.num_moves) = (x, y, num_moves)

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def __hash__(self):
		return hash((self.x, self.y))
n = int(input().strip())

def get_moves(x, y, num_moves, a, b):
	moves = []
	if x + a < n:
		if y + b < n:
			moves.append(state(x + a, y + b, num_moves))
		if y - b >= 0:
			moves.append(state(x + a, y - b, num_moves))
	if x - a >= 0:
		if y + b < n:
			moves.append(state(x - a, y + b, num_moves))
		if y - b >= 0:
			moves.append(state(x - a, y - b, num_moves))
	if x + b < n:
		if y + a < n:
			moves.append(state(x + b, y + a, num_moves))
		if y - a >= 0:
			moves.append(state(x + b, y - a, num_moves))
	if x - b >= 0:
		if y + a < n:
			moves.append(state(x - b, y + a, num_moves))
		if y - a >= 0:
			moves.append(state(x - b, y - a, num_moves))
	return moves

def bfs(a, b):
	visited = set()
	fringe = queue.Queue()
	start = state(0, 0, 0)
	goal = state(n - 1, n - 1, None)
	visited.add(start)
	fringe.put(start)
	while not fringe.empty():
		current = fringe.get()
		if current == goal:
			return current.num_moves
		for move in get_moves(current.x, current.y, current.num_moves + 1, a, b):
			if move not in visited:
				visited.add(move)
				fringe.put(move)
	return -1
for i in range(1, n):
	for j in range(1, n):
		print(bfs(i, j), end=' ')
	print()


import sys
import queue as queue
n = int(input().strip())

def findRequiredSteps(a, b, n):
	s = set([])
	q = queue.Queue()
	adjNodesCalc = []
	adjNodes = []
	rs = set([(0, 0)])
	root = (0, 0)
	rounds = 0
	target = (n - 1, n - 1)
	s.add(root)
	q.put(root)
	while q.empty() != True:
		current = q.get()
		(xcor, ycor) = (current[0], current[1])
		if current not in rs:
			rounds += 1
			rs = rs | set(adjNodesCalc)
			adjNodesCalc = []
		adjNodes = list(filter(lambda x: 0 <= x[0] < n and 0 <= x[1] < n, [(xcor - a, ycor + b), (xcor - a, ycor - b), (xcor + a, ycor - b), (xcor - b, ycor + a), (xcor - b, ycor - a), (xcor + b, ycor - a), (xcor + a, ycor + b), (xcor + b, ycor + a)]))
		adjNodesCalc.extend(adjNodes)
		if target in adjNodes:
			rounds += 1
			return rounds
		for node in adjNodes:
			if node not in s:
				s.add(node)
				q.put(node)
	return -1
for i in range(1, n):
	for j in range(1, n):
		print(findRequiredSteps(i, j, n), end=' ')
	print('\n', end='')


def minMove(n, a, b):
	positionsToProcess = [[0, 0]]
	knightMoves = [[a, b], [a, -1 * b], [-1 * a, b], [-1 * a, -1 * b], [b, a], [b, -1 * a], [-1 * b, a], [-1 * b, -1 * a]]
	visitedPositions = []
	distance = 0
	while len(positionsToProcess) != 0:
		temp = []
		distance += 1
		for position in positionsToProcess:
			for move in range(8):
				newPosition = [position[0] + knightMoves[move][0], position[1] + knightMoves[move][1]]
				if newPosition[0] >= 0 and newPosition[0] <= n - 1:
					if newPosition[1] >= 0 and newPosition[1] <= n - 1:
						if newPosition not in visitedPositions and newPosition not in temp:
							if newPosition == [n - 1, n - 1]:
								return distance
							else:
								temp.append(newPosition)
		visitedPositions += positionsToProcess
		positionsToProcess = temp
	return -1
n = int(input())
for a in range(1, n):
	for b in range(1, n):
		answer = minMove(n, a, b)
		print(answer, end=' ')
	print()


import sys

def get_frontier(cur, level, i, j, n):
	frontier = []
	for k in [-i, i]:
		for m in [-j, j]:
			for (p1, p2) in [(cur[0] + k, cur[1] + m), (cur[0] + m, cur[1] + k)]:
				if 0 <= p1 <= n - 1 and 0 <= p2 <= n - 1 and ((p1, p2) not in level):
					frontier.append((p1, p2))
	return frontier

def reach(fr, to, i, j, n):
	dist = 0
	level = {fr: dist}
	dist += 1
	frontier = get_frontier(fr, level, i, j, n)
	while frontier:
		nxt = []
		for p in frontier:
			if p not in level:
				level[p] = dist
				if p == to:
					return (dist, level)
				p_frontier = get_frontier(p, level, i, j, n)
				nxt.extend(p_frontier)
		dist += 1
		frontier = nxt
	return (-1, level)

def min_reach(n, i, j):
	(fr, to) = ((0, 0), (n - 1, n - 1))
	(m, level) = reach(fr, to, i, j, n)
	return m

def print_ans(ans):
	for row in ans:
		str_row = ' '.join((str(c) for c in row))
		print(str_row)

def enter_data():
	n = int(input().strip())
	ans = []
	for i in range(1, n):
		row = []
		for j in range(1, n):
			m = min_reach(n, i, j)
			row.append(m)
		ans.append(row)
	return ans
ans = enter_data()
print_ans(ans)


import sys
from itertools import combinations
import collections

def FindMin(n, a, b):
	found = {}
	Combos = [[0, 0]]
	depth = 0
	while len(Combos) > 0:
		newCombos = {}
		for loc in Combos:
			currentKey = '{}x{}'.format(loc[0], loc[1])
			if loc[0] == n - 1 and loc[1] == n - 1:
				return depth
			else:
				found[currentKey] = 1
				newCombos['{}x{}'.format(loc[0] + a, loc[1] + b)] = [loc[0] + a, loc[1] + b]
				newCombos['{}x{}'.format(loc[0] + a, loc[1] - b)] = [loc[0] + a, loc[1] - b]
				newCombos['{}x{}'.format(loc[0] - a, loc[1] + b)] = [loc[0] - a, loc[1] + b]
				newCombos['{}x{}'.format(loc[0] - a, loc[1] - b)] = [loc[0] - a, loc[1] - b]
				newCombos['{}x{}'.format(loc[0] + b, loc[1] + a)] = [loc[0] + b, loc[1] + a]
				newCombos['{}x{}'.format(loc[0] + b, loc[1] - a)] = [loc[0] + b, loc[1] - a]
				newCombos['{}x{}'.format(loc[0] - b, loc[1] + a)] = [loc[0] - b, loc[1] + a]
				newCombos['{}x{}'.format(loc[0] - b, loc[1] - a)] = [loc[0] - b, loc[1] - a]
		depth += 1
		Combos = []
		for key in newCombos:
			combo = newCombos[key]
			if (combo[0] > n - 1 or combo[0] < 0) or (combo[1] > n - 1 or combo[1] < 0):
				continue
			elif key in found:
				continue
			else:
				Combos.append(combo)
	return -1
n = int(input().strip())
output = [[0 for x in range(n - 1)] for y in range(n - 1)]
for i in range(0, n - 1):
	for j in range(i, n - 1):
		output[i][j] = FindMin(n, i + 1, j + 1)
		output[j][i] = output[i][j]
for item in output:
	print(' '.join(map(str, item)))


import sys
from collections import deque

def getdxdy(a, b):
	if a == b:
		return [(-a, -b), (-a, b), (a, -b), (a, b)]
	else:
		return [(-a, -b), (-a, b), (a, -b), (a, b), (-b, -a), (-b, a), (b, -a), (b, a)]

def search(n, a, b):
	d = deque([(0, 0, 0)])
	m = [0 for i in range(n * n)]
	while len(d) > 0:
		(x, y, level) = d.popleft()
		m[n * x + y] = 1
		for (dx, dy) in getdxdy(a, b):
			next_x = x + dx
			next_y = y + dy
			if 0 <= next_x < n and 0 <= next_y < n and (m[n * next_x + next_y] == 0):
				d.append((next_x, next_y, level + 1))
				m[n * next_x + next_y] = 1
			if next_x == n - 1 and next_y == n - 1:
				return level + 1
	return -1
n = int(input().strip())
ans = [[0 for i in range(n)] for j in range(n)]
for a in range(1, n):
	for b in range(a, n):
		ans[a][b] = ans[b][a] = search(n, a, b)
for i in range(1, n):
	for j in range(1, n):
		print(ans[i][j], end=' ')
	print('')


import collections as col

class CNode:

	def __init__(self, x, y):
		self.x = x
		self.y = y
		self.distance = None
		self.parent = None

	def get_poss_moves(self, a, b, n):
		pmoves = []
		for (i, j) in [(self.x + a, self.y + b), (self.x + b, self.y + a), (self.x - a, self.y + b), (self.x - b, self.y + a), (self.x + a, self.y - b), (self.x + b, self.y - a), (self.x - a, self.y - b), (self.x - b, self.y - a)]:
			if 0 <= i < n and 0 <= j < n:
				if (i, j) not in pmoves:
					pmoves.append((i, j))
		return pmoves

	def __hash__(self):
		return hash((self.x, self.y))

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def __str__(self):
		return str('{},{} : {}'.format(self.x, self.y, self.distance))

class CTree:

	def __init__(self, cnode, a, b, n):
		self.root = cnode
		self.a = a
		self.b = b
		self.n = n
		self.dx = n - 1
		self.dy = n - 1
		self.visited = []

	def do_search(self, node):
		S = set()
		Q = col.deque()
		S.add(node)
		Q.appendleft(node)
		while len(Q) > 0:
			current = Q.pop()
			if current.x == self.dx and current.y == self.dy:
				current.distance = 0
				lpnode = current
				while lpnode is not None:
					if lpnode.parent:
						lpnode.parent.distance = lpnode.distance + 1
						lpnode = lpnode.parent
					else:
						lpnode = None
				return current
			else:
				pmoves = current.get_poss_moves(self.a, self.b, self.n)
				for p in pmoves:
					pnode = CNode(p[0], p[1])
					if pnode not in S:
						S.add(pnode)
						pnode.parent = current
						Q.appendleft(pnode)

def do_walk(x, y, a, b, n):
	cnode = CNode(x, y)
	ctree = CTree(cnode, a, b, n)
	fnode = ctree.do_search(cnode)
	return cnode.distance if cnode.distance is not None else -1
nb = int(input())
for i in range(1, nb):
	rl = []
	for j in range(1, nb):
		rl.append(str(do_walk(0, 0, i, j, nb)))
	print(' '.join(rl))


import sys
n = int(input().strip())
A = []
for a in range(1, n):
	B = []
	for b in range(1, n):
		P = {(0, 0)}
		c = 0
		f = True
		V = set()
		while f:
			c += 1
			Q = set()
			V = V | P
			for p in P:
				if (p[0] == n - 1) & (p[1] == n - 1):
					f = False
					break
				if (0 <= p[0] + a < n) & (0 <= p[1] + b < n):
					Q.add((p[0] + a, p[1] + b))
				if (0 <= p[0] - a < n) & (0 <= p[1] - b < n):
					Q.add((p[0] - a, p[1] - b))
				if (0 <= p[0] - a < n) & (0 <= p[1] + b < n):
					Q.add((p[0] - a, p[1] + b))
				if (0 <= p[0] + a < n) & (0 <= p[1] - b < n):
					Q.add((p[0] + a, p[1] - b))
				if (0 <= p[0] + b < n) & (0 <= p[1] + a < n):
					Q.add((p[0] + b, p[1] + a))
				if (0 <= p[0] - b < n) & (0 <= p[1] - a < n):
					Q.add((p[0] - b, p[1] - a))
				if (0 <= p[0] - b < n) & (0 <= p[1] + a < n):
					Q.add((p[0] - b, p[1] + a))
				if (0 <= p[0] + b < n) & (0 <= p[1] - a < n):
					Q.add((p[0] + b, p[1] - a))
			P = set()
			P = P | Q
			P = P - V
			if len(P) == 0:
				break
		if not f:
			B.append(c - 1)
		else:
			B.append(-1)
	A.append(B)
for a in A:
	for b in a:
		print(b, end=' ')
	print('')


import sys
import collections as q
results = {}
n = int(input().strip())
for i in range(1, n):
	for j in range(i, n):
		directions = [(i, j), (i, -j), (-i, j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
		num_moves = 0
		moves = q.deque([(1, 1, 0)])
		visited = {(1, 1)}
		while moves and num_moves == 0:
			m = moves.pop()
			for d in directions:
				lr = m[0] + d[0]
				ud = m[1] + d[1]
				if lr == n and ud == n:
					num_moves = m[2] + 1
					break
				elif 1 <= lr and lr <= n and (1 <= ud) and (ud <= n) and ((lr, ud) not in visited):
					moves.appendleft([lr, ud, m[2] + 1])
					visited.add((lr, ud))
		results[i, j] = num_moves
for i in range(1, n):
	for j in range(1, n):
		if i <= j and results[i, j]:
			print(results[i, j], end=' ')
		elif i > j and results[j, i]:
			print(results[j, i], end=' ')
		else:
			print(-1, end=' ')
		if j == n - 1:
			print()


import sys
import collections

def min_moves(n, a, b):
	visited = set()
	queue = collections.deque()
	queue.appendleft((0, 0, 0))
	while queue:
		(x, y, l) = queue.popleft()
		if x == n - 1 and y == n - 1:
			return l
		for nextX in [x + a, x - a]:
			for nextY in [y + b, y - b]:
				if 0 <= nextX < n and 0 <= nextY < n and (not (nextX, nextY) in visited):
					visited.add((nextX, nextY))
					queue.append((nextX, nextY, l + 1))
		for nextX in [x + b, x - b]:
			for nextY in [y + a, y - a]:
				if 0 <= nextX < n and 0 <= nextY < n and (not (nextX, nextY) in visited):
					visited.add((nextX, nextY))
					queue.append((nextX, nextY, l + 1))
	return -1
n = int(input().strip())
for a in range(1, n):
	for b in range(1, n):
		print(min_moves(n, a, b), end=' ')
	print()


from queue import PriorityQueue

def reach(i, j):
	seen = set()
	seen.add((0, 0))
	q = PriorityQueue()
	q.put((0, 0, 0))
	while not q.empty():
		(p, curx, cury) = q.get()
		if curx == n - 1 and cury == n - 1:
			return p
		if curx >= i and cury >= j and ((curx - i, cury - j) not in seen):
			q.put((p + 1, curx - i, cury - j))
			seen.add((curx - i, cury - j))
		if curx >= i and cury < n - j and ((curx - i, cury + j) not in seen):
			q.put((p + 1, curx - i, cury + j))
			seen.add((curx - i, cury + j))
		if curx >= j and cury >= i and ((curx - j, cury - i) not in seen):
			q.put((p + 1, curx - j, cury - i))
			seen.add((curx - j, cury - i))
		if curx >= j and cury < n - i and ((curx - j, cury + i) not in seen):
			q.put((p + 1, curx - j, cury + i))
			seen.add((curx - j, cury + i))
		if curx < n - i and cury >= j and ((curx + i, cury - j) not in seen):
			q.put((p + 1, curx + i, cury - j))
			seen.add((curx + i, cury - j))
		if curx < n - i and cury < n - j and ((curx + i, cury + j) not in seen):
			q.put((p + 1, curx + i, cury + j))
			seen.add((curx + i, cury + j))
		if curx < n - j and cury >= i and ((curx + j, cury - i) not in seen):
			q.put((p + 1, curx + j, cury - i))
			seen.add((curx + j, cury - i))
		if curx < n - j and cury < n - i and ((curx + j, cury + i) not in seen):
			q.put((p + 1, curx + j, cury + i))
			seen.add((curx + j, cury + i))
	return -1
n = int(input())
for i in range(1, n):
	for j in range(1, n):
		print(reach(i, j), end=' ')
	print()


import sys
n = int(input().strip())

def allmoves(i, j, a, b, n):
	moves = []
	deltas = [(a, b), (a, -b), (-a, b), (-a, -b)]
	deltas.extend([(b, a), (b, -a), (-b, a), (-b, -a)])
	for delta in deltas:
		if i + delta[0] >= 0 and i + delta[0] < n and (j + delta[1] >= 0) and (j + delta[1] < n):
			moves.append((i + delta[0], j + delta[1]))
	return moves

def finddist(n, a, b):
	dist = [[-1 for x in range(n)] for x in range(n)]
	dist[n - 1][n - 1] = 0
	todo = [(n - 1, n - 1)]
	while len(todo) > 0:
		(i, j) = todo.pop(0)
		newmoves = allmoves(i, j, a, b, n)
		for move in newmoves:
			if dist[move[0]][move[1]] == -1:
				dist[move[0]][move[1]] = dist[i][j] + 1
				todo.append((move[0], move[1]))
				if move[0] == 0 and move[1] == 0:
					break
	return dist[0][0]
ans = [[0 for x in range(n - 1)] for x in range(n - 1)]
for i in range(n - 1):
	for j in range(n - 1):
		ans[i][j] = finddist(n, i + 1, j + 1)
for i in range(n - 1):
	print(' '.join(map(str, ans[i])))


import sys
from collections import deque

def knight(n, a, b):
	M = [[-1] * n for i in range(n)]
	M[0][0] = 0
	queue = deque([(0, 0)])
	while queue:
		(x, y) = queue.popleft()
		for i in [x - a, x + a]:
			for j in [y - b, y + b]:
				if 0 <= i < n and 0 <= j < n and (M[i][j] == -1):
					M[i][j] = M[x][y] + 1
					queue.append((i, j))
		for i in [x - b, x + b]:
			for j in [y - a, y + a]:
				if 0 <= i < n and 0 <= j < n and (M[i][j] == -1):
					M[i][j] = M[x][y] + 1
					queue.append((i, j))
	return M[n - 1][n - 1]
n = int(input().strip())
M = [[None] * (n - 1) for i in range(n - 1)]
for i in range(n - 1):
	for j in range(i, n - 1):
		M[i][j] = M[j][i] = knight(n, i + 1, j + 1)
	print(*M[i], sep=' ')


import sys
from collections import deque

def moves(i, j, k, l, n):
	result = []
	result.extend(((i0, j0) for i0 in (i - k, i + k) for j0 in (j - l, j + l) if 0 <= i0 < n and 0 <= j0 < n))
	result.extend(((i0, j0) for i0 in (i - l, i + l) for j0 in (j - k, j + k) if 0 <= i0 < n and 0 <= j0 < n))
	return result

def index(i, j, n):
	return n * i + j

def pos(kk, n):
	return (k // n, k % n)

def main():
	n = int(input().strip())
	min_moves = [-1] * n ** 2
	for k in range(1, n):
		for l in range(k, n):
			board = [-1] * n ** 2
			board[0] = 0
			queue = deque([(0, (0, 0))])
			while queue and queue[-1][1] != (n - 1, n - 1):
				(nmoves, (i, j)) = queue.pop()
				nmoves += 1
				for (i0, j0) in moves(i, j, k, l, n):
					ind = index(i0, j0, n)
					if board[ind] < 0 or board[ind] > nmoves:
						board[ind] = nmoves
						queue.appendleft((nmoves, (i0, j0)))
			min_moves[index(k, l, n)] = min_moves[index(l, k, n)] = board[index(n - 1, n - 1, n)]
	for k in range(1, n):
		print(*min_moves[k * n + 1:k * n + n])
main()


import collections
n = int(input())
grid = [[-1] * (n - 1) for i in range(n - 1)]
for i in range(1, n):
	for j in range(i, n):
		seen = [[0] * n for i in range(n)]
		active = collections.deque()
		active.append((0, n - 1, n - 1))
		while active:
			(s, x, y) = active.popleft()
			if x == 0 and y == 0:
				grid[i - 1][j - 1] = s
				grid[j - 1][i - 1] = s
				break
			if x < 0 or y < 0 or x >= n or (y >= n) or seen[y][x]:
				continue
			seen[y][x] = 1
			seen[x][y] = 1
			s += 1
			active.extend([(s, x + i, y + j), (s, x + i, y - j), (s, x - i, y + j), (s, x - i, y - j), (s, x + j, y + i), (s, x + j, y - i), (s, x - j, y + i), (s, x - j, y - i)])
for row in grid:
	print(' '.join([str(x) for x in row]))