Interesting Pyramid

Sathi is an intelligent girl. She likes to play with mathematical problems. Everyday she makes some new interesting problems by herself and then tries to solve it. But, some problems take too much time in finding out the desired result and she can’t even make herself sure about this result. So, recently she learned about programming and she also learned that every mathematical problem can be solved by computer too accurately and very quickly by building correct programs for it.

Today, she comes up with a new interesting pyramid problem. There are $N$ integers ($N$ is always an odd number) in the first row and every next row, the numbers decrease exactly by two each time compared to the previous row and the last row has exactly one integer. (see in Fig-1) Then, she draws some combination lines (Fig-1) on it and gets some series of numbers. She keeps a record of all sum of these series and finds out the maximum one.

1st series $sum = 24 + 10 + 0 + 10 + 24 = 68$
2nd series $sum = 12 + 10 + 12 = 34$ 3rd series $sum = 12 = 12$
So, among all sums, 68 is the maximum.

After finding this out, Sathi now wants to write a program to check whether her answer is right or not. But, soon she realizes that it is not so easy to write such a program as she is not that much expert yet. So, now your task is to help Sathi by writing such a program in which Sathi can check the maximum sum of any such interesting pyramids she makes.

Input

There will be multiple test cases in each input file where each test case represents a new such pyramid.

First line will contain an odd number $N$ ($1 < N < 100$), denoting the number of integers of the first row of pyramids. Each pyramid contains exactly $N/2+1$ rows where each row contains exactly two less number of integers compared to the previous row and the last row contains exactly one integer. No integer will exceed $10^3$.

The input file will be terminated when $N = 0$ and each input file will contain at most 30 test cases.

Output

For each case, print the maximum sum in a new line by the process that is already defined above.

Sample

Input	Output
5 24 12 12 12 24 10 10 10 0 0	68