A quadrilateral is a simple geometric shape. The formal definition of Quadrilateral for this problem can be given as

“A quadrilateral is a simple polygon with four sides, having a strictly positive area.”

If you are given four rods made of steel and having integer length, you may or may not be able to make a quadrilateral with it. For example you cannot make a quadrilateral with four rods of length 4, 5, 8 and 17 units but you can make a quadrilateral with four rods of length 2, 3, 4 and 5 units respectively. Now you have to supply n rods to the Architecture department of a University. But the University authority has asked you to make the length of the rods such that no four of them can be used to make a Quadrilateral. They are afraid that if the students can make such shapes then they will use up some of the rods in the sculptures they make. Given the value of n, what is the minimum possible length of the longest rod? You can assume that:

1. Only one rod has to be used as one side of the Quadrilateral.
2. A rod cannot be divided into two smaller pieces.
3. Two or more rods cannot be joined to make a longer rod.

Input

The input file contains around 100 line of input. Each line contains an integer, which denotes the value of n (3<n<61). A line containing a 0 (zero) terminates the input.

Output

For each line of input produce one line of output. This line contains serial of output followed by a decimal integer that denotes the shortest possible length of longest rod. You can safely assume that this length will fit in a 64-bit signed integer. Look at the output for sample input for details.

Sample Input                                Output for Sample Input

Illustration of first Sample Input: If you have four sticks of length 1, 1, 1 and 3 then you cannot make a quadrilateral with them. So when n=4, the minimum possible length of the longest rod is 3.

Problemsetter: Shahriar Manzoor, Special Thanks: A. Arif, S. Hafiz, M. R. Khan, D. Kisman

題目描述：

學生很貪玩，總是喜歡把棒子拼成四邊形。

為了防止他們這麼作，想要讓所有棒子任挑 4 個都湊不成四邊形。

問當有 n 個棒子時，最小的最長棒子長度為何？

題目解法：

很明顯地是遞迴關係，一定會延續前一個情況。

那麼新的最長棒子一定是之前最長的前三個棒子長度加起來，剛好沒辦法湊成四邊形。

#include <stdio.h>

int main() {
    long long dp[64] = {0,1,1,1};
    int i, cases = 0;
    for(i = 4; i < 64; i++)
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
    while(scanf("%d", &i) == 1 && i)
        printf("Case %d: %lld\n", ++cases, dp[i]);
    return 0;
}