문제

'이집트인처럼 걷기'는 사하라 유목 민족 아이들이 하던 다인용 옛날 보드 게임입니다. 옛날로 돌아가, 아이들이 돌을 모아 각각에 번호를 붙입니다. N명이 게임을 하려면 N²개의 돌이 필요합니다. 각 플레이어는 N개의 돌을 고릅니다. 이후 돌을 (N = 4 기준) 그림 (a)와 같이 이상한 순서로 N x N 격자에 배치합니다. 오른쪽 위 모서리에 돌이 놓인 플레이어가 라운드에서 패배합니다. 이후 N-1명으로 다음 라운드가 시작됩니다. 우승자를 정하기 위해서는 총 N-1번 라운드를 진행해야 합니다.

왜 이렇게 이상한 순서로 돌이 놓이는지 가설이 하나 있습니다. 파라오 시절에 피라미드의 암실에 들어가면, 노동자는 동료를 잃어버리지 않고 방을 걷기 위해 아래의 "알고리즘"을 사용했다고 합니다: (그림 (b) 참고)

1. 첫 번째 노동자가 방의 왼쪽 아래 모서리에 섭니다.

2. 다음 세 명의 노동자가 첫 번째 노동자에 주위에 시계 반대 방향으로 들어가 서 사분원을 형성합니다.

3. 다음 다섯 명의 노동자가 이전 세 명의 노동자 주위에 이번에는 시계 방향으로 들어가 서 사분원을 형성합니다.

4. 방이 노동자로 가득 찰 때까지 이전의 두 단계를 반복합니다. 왼쪽이나 아래 벽을 칠 때마다, 더 큰 사분원을 시작하고 방향을 시계 반대 방향 또는 시계 방향으로 전환합니다.

오른쪽 위 모서리에 놓인 돌이 무엇인지 계산하는 프로그램을 작성합시다.

입력

 프로그램은 하나 이상의 테스트 케이스로 검증됩니다. 각 테스트 케이스는 별개의 줄로 주어집니다. 각 테스트 케이스에는 0 < N < 1,000을 만족하며 플레이어의 수를 나타내는 N이 주어집니다.

테스트 케이스 끝에 하나의 0으로 이루어진 줄이 주어지며 종료됩니다.

출력

 각 테스트 케이스에 대해, 아래의 형식으로 한 줄에 결과를 출력합니다:

N => 결과

N은 테스트 케이스의 플레이어의 수이며, 결과는 격자 오른쪽 위 모서리에 놓인 돌의 번호입니다.