이집트인처럼 걷기

Walk Like an Egyptian은 옛날 사하라 유목 부족의 아이들이 즐기던 오래된 보드게임이다. 아이들은 돌을 모아 각 돌에 번호를 매겼다. 참가자가 $N$명인 게임에는 $N^2$개의 돌이 필요하며, 각 참가자는 그중 $N$개를 고른다. 돌은 그림 (a)와 같은 독특한 순서로 $N \times N$ 격자 위에 놓인다(그림은 $N = 4$인 경우이다). 자신의 돌이 오른쪽 위 모서리에 놓인 참가자가 그 라운드에서 진다. 이어서 $N - 1$명으로 다음 라운드를 진행하며, 모두 $N - 1$번의 라운드를 거쳐 우승자를 가린다.

돌을 놓는 순서는, 피라미드 안의 어두운 방을 아무도 잃지 않고 지나가기 위해 옛날 파라오의 일꾼들이 쓰던 규칙을 따른다(그림 (b) 참고).

1. 첫 번째 일꾼은 방의 왼쪽 아래 모서리에 선다.
2. 다음 세 명은 첫 번째 일꾼을 둘러싸며 반시계 방향으로 사분원(1/4 원)을 이룬다.
3. 그다음 다섯 명은 그 세 명을 둘러싸며, 이번에는 시계 방향으로 사분원을 이룬다.
4. 방이 가득 찰 때까지 위의 두 단계를 반복한다. 왼쪽 벽이나 아래쪽 벽에 닿을 때마다 더 큰 사분원을 새로 시작하고, 방향을 시계 방향과 반시계 방향으로 번갈아 바꾼다.

돌에는 일꾼들이 자리를 잡는 순서 그대로 $1, 2, 3, \ldots, N^2$의 번호가 매겨진다. $N$이 주어질 때, 격자의 오른쪽 위 모서리에 놓이는 돌의 번호를 구하여라.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 참가자 수를 나타내는 정수 $N$ ($0 < N < 1000$) 하나로 주어진다.

입력의 끝은 $0$ 하나만 있는 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 N => result 형식으로 한 줄씩 출력한다. 여기서 $N$은 해당 테스트 케이스의 참가자 수이고, result는 격자의 오른쪽 위 모서리에 놓인 돌의 번호이다.