5346번 - Frodo Sequence 다국어

문제

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

• Fib₁ = 1
• Fib₂ = 1
• Fib₃ = 2
• Fib₄ = 3
• Fib₅ = 5
• …
• 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 called the Frodo sequence. Frodo’s sequence is defined as follows:

• Fro₁ = 1
• Fro₂ = 1
• Fro₃ = 2
• Fro₄ = 2
• Fro₅ = 3
• …
• Fro_n = Fro_n-1 + Fro_n-2 - Fro_n-3 for all n>3

You need to write a program that given n finds Fro_n.

입력

he input will be a sequence of integers, one per line. The end of input will be signaled by the integer 0. All integers, other than the last (zero), are positive and less than 2³¹.

출력

For each positive integer, n, print Fro_n.

제한

힌트