2015 HIAST Collegiate Programming Contest H

A sequence of positive and non-zero integers called palindromic if it can be read the same forward and backward, for example:

15 2 6 4 6 2 15

20 3 1 1 3 20

We have a special kind of palindromic sequences, let's call it a special palindrome.

A palindromic sequence is a special palindrome if its values don't decrease up to the middle value, and of course they don't increase from the middle to the end.

The sequences above is NOT special, while the following sequences are:

1 2 3 3 7 8 7 3 3 2 1

2 10 2

1 4 13 13 4 1

Let's define the function F(N), which represents the number of special sequences that the sum of their values is N.

For example F(7) = 5 which are : (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)

Your job is to write a program that compute the Value F(N) for given N's.

Input

The Input consists of a sequence of lines, each line contains a positive none zero integer N less than or equal to 250. The last line contains 0 which indicates the end of the input.

Output

Print one line for each given number N, which it the value F(N).

Example

Input

1
3
7
10
0

Output1

2
5
17
解题思路：
要求一个数能分解成的回文串的数量，首先他要想成为回文串，左右两边必须相等，奇偶性讨论：
1.当n为奇数时，有中间数字，且必为奇数，因为两边相等加起来必为偶数，那么中间的数字必为小于等于n的奇数，遍历中间数，对其中一边进行整数划分
2.当n为偶数是，有两种情况:
(1).n所化成的回文串长度为奇数，那么中间数必为偶数，直接按上面遍历划分就行，
(2).回文串长度为偶数时，直接对n/2进行整数划分。两种情况的值加起来就是n为偶数是能分解成的回文串数量
注意：整数划分最好不要用递归法，效率太低了，很容易超时。用dp打表还是比较稳的。而且数值比较大最好用long long。
实现代码：

#include<bits/stdc++.h>
using namespace std;
#define Max 255
#define ll long long
ll f[Max][Max];
void fun(){
    for(int i=1;i<251;i++){
        for(int j=1;j<251;j++){
            if(i==0||j==0) f[i][j] = 0;
            else if(i==1||j==1) f[i][j] = 1;
            else if(i<j) f[i][j] = f[i][i];
            else if(i==j) f[i][j] = f[i][j-1] + 1;
            else f[i][j] = f[i-j][j] + f[i][j-1];
        }
    }
}
int main()
{
    ll ans,n,i;
    fun();
    //cout<<f[250][250]<<endl;
    while(cin>>n&&n){
            ans = 1;
        if(n%2==1){
            for(i=1;i<=n;i+=2){
                ans+=f[(n-i)/2][i];
            }
        }
        else{
            for(i=2;i<=n;i+=2){
                ans+=f[(n-i)/2][i];
            }
              ans+=f[n/2][n/2];
        }
        cout<<ans<<endl;
    }
    return 0;
}