学步园

#include<stdio.h>

int f[1005][6000],len[1005];
int main()
{
    f[1][0]=f[2][0]=1;
    len[1]=len[2]=1;
    int i,j,c;
    for(i=3;i<=1000;i++)
    {
        c=0;len[i]=len[i-1];
         for(j=0;j<len[i];j++)
         {
             f[i][j]=f[i-1][j]+f[i-2][j]+c;
             c=f[i][j]/10;
             f[i][j]%=10;
             if(c&&len[i]==j+1)
             len[i]++;
         }
    }
    int n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=len[n]-1;i>=0;i--)
        printf("%d",f[n][i]);
        printf("\n");
    }
    return 0;
}