http://acm.hdu.edu.cn/showproblem.php?pid=2512
//1290997 2009-04-20 16:28:41 Accepted 2512 62MS 14012K 545 B C++ no way 
#include<iostream>
using namespace std;
const int N=2001;
int dp[N][N];//dp[i][j]表示i张卡片分成j堆的情况数
int main()
{
    int t,i,j;
    int num[N];

    for(i=1;i<=N-1;i++)
        dp[i][i] = dp[i][1] = 1;

    for(j=2;j<N-1;j++)//堆数
        for(i=j+1;i<=N-1;i++)//卡片数
            dp[i][j] =( (dp[i-1][j] * j)%10000 + dp[i-1][j-1] ) % 10000;

    for(i=1;i<=N-1;i++)
    {
        num[i] = 0;
        for(j=1;j<=i;j++)
        {
            num[i] += dp[i][j];
            num[i] %= 10000;
        }
        num[i] %= 1000;
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&i);
        printf("%d\n",num[i]);
    }
    return 0;
}