Recaman sequence 는 다음과 같이 정의 된다.

• a₀ = 0
• m > 0 인 경우 a_m-1 - m > 0 이고 이미 나온 수가 아니면 a_m = a_m-1 - m 아니면 a_m = a_m-1 + m

k 가 주어질 때 ak 를 구하는 것이 문제이다.

입력

입력은 끝은 -1 이다.

출력

입출력 예

입력

7
10000
-1

출력

20
18658

출처: Shanghai 2004 Preliminary