프로도 수열

피보나치 수열은 1202년 레오나르도 피사노(피보나치)가 정의한 유명한 정수 수열로, 다음과 같이 정의된다.

• $Fib_1 = 1$
• $Fib_2 = 1$
• $Fib_3 = 2$
• $Fib_4 = 3$
• $Fib_5 = 5$
• $\dots$
• 모든 $n > 2$에 대해 $Fib_n = Fib_{n-1} + Fib_{n-2}$

잘 알려지지 않았지만, 골목쟁이집의 프로도 역시 프로도 수열이라는 정수 수열을 정의했다. 프로도 수열은 다음과 같이 정의된다.

• $Fro_1 = 1$
• $Fro_2 = 1$
• $Fro_3 = 2$
• $Fro_4 = 2$
• $Fro_5 = 3$
• $\dots$
• 모든 $n > 3$에 대해 $Fro_n = Fro_{n-1} + Fro_{n-2} - Fro_{n-3}$

정수 $n$이 주어질 때 $Fro_n$을 구하는 프로그램을 작성하시오.

입력은 한 줄에 하나씩 주어지는 정수들의 수열이다. 입력의 끝은 정수 $0$으로 표시된다. 마지막 $0$을 제외한 모든 정수는 양수이며 $2^{31}$보다 작다.

각 양의 정수 $n$에 대해 $Fro_n$을 한 줄에 하나씩 출력한다.