Virus Outbreak

Interview

Time limit2sMemory limit512 MB

Summary

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

Level: Easy3 of 10
Topics: Math, Dynamic programming, Implementation, Recursion
Solved: No attempts yet

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) = 1$ , $a(2) = 1$ , and $a(n) = a(n-1) + a(n-2)$ for every $n \ge 3$ , write a program that computes the cumulative count $a(X)$ for a given hour $X$ .

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.

Examples1

Example 1

Input

Expected output

Hour 1: 1 cow(s) affected
Hour 4: 3 cow(s) affected
Hour 6: 8 cow(s) affected
Hour 11: 89 cow(s) affected