Virus Outbreak

Read hour values until -1 and print the Fibonacci number a(X) for each in the format 'Hour X: Y cow(s) affected'.

Easy3MathDynamic programmingImplementationRecursionInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

The veterinary authority has reported an outbreak of a newly discovered cattle disease. Every affected cow has been euthanized to protect the industry. The cumulative numbers of affected cows after 8, 9, and 10 hours were 21, 34, and 55 respectively.

The counts follow the Fibonacci sequence. With a(1)=1a(1) = 1, a(2)=1a(2) = 1, and a(n)=a(n1)+a(n2)a(n) = a(n-1) + a(n-2) for every n3n \ge 3, write a program that computes the cumulative count a(X)a(X) for a given hour XX.

Input

The input consists of several lines. Each line contains one positive integer no greater than 490, representing an hour. The last line contains -1, which terminates the input and must not be processed.

Output

For each input value, print one line in the format Hour X: Y cow(s) affected, where X is the given hour and Y is the cumulative number of affected cows at that hour.