Migrated from Lutece 624 整数划分

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一个整数可以写成多个整数相加的形式，比如$4$可以写成以下形式

$4=4$

$4=3+1$

$4=2+2$

$4=2+1+1$

$4=1+1+1+1$

注意 $4=3+1$和$4=1+3$是一样的，现在多加一个要求，即等式右边的数不能相同，比如对于$4$来说，后面$3$种划分方式是不符合要求的，现在给定一个$N$，问有多少种划分方法，答案$mod\ 19901014$

Input

第一行有个整数$T$，代表数据组数（$T\leq 10000$）

接下来有$T$行，每行有个整数$N$ ($1\leq N\leq 1000$)

Output

输出$T$行，每行输出一个整数，代表$N$的划分数 $mod\ 19901014$

Samples

3
4
5
10

2
3
10

Resources

UESTC Training for Math