Frodo Sequence

The Fibonacci sequence is a famous integer sequence defined by Leonardo of Pisa in 1202. It is defined as follows:

• $Fib_1 = 1$
• $Fib_2 = 1$
• $Fib_3 = 2$
• $Fib_4 = 3$
• $Fib_5 = 5$
• $\dots$
• $Fib_n = Fib_{n-1} + Fib_{n-2}$ for all $n > 2$

What you may not know is that Frodo of Bag End also defined an integer sequence, the Frodo sequence. It is defined as follows:

• $Fro_1 = 1$
• $Fro_2 = 1$
• $Fro_3 = 2$
• $Fro_4 = 2$
• $Fro_5 = 3$
• $\dots$
• $Fro_n = Fro_{n-1} + Fro_{n-2} - Fro_{n-3}$ for all $n > 3$

Given $n$, write a program that finds $Fro_n$.

The input is a sequence of integers, one per line. The end of input is signaled by the integer $0$. Every integer other than the final $0$ is positive and less than $2^{31}$.

For each positive integer $n$, print $Fro_n$ on its own line.