Problem1934--Value

1934: Value

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

TC对一个数X的value计算方法如下: 

把X拆分为若干个两两不同的素数,不同方案数即为X的value。 

如7可以拆分为1个7或者2、5,故7的value为2。 

给定一个数X,请你来帮TC计算value。 

Input

第一行为T(T<=30), 

接下来T行,每行输入一个整数X(X<=5000)。 

Output

输出T行, 每行一个整数,表示X的value(答案对109+7取模)。 

Sample Input Copy

1
7

Sample Output Copy

2

HINT

7=2+2+3不符合要求,存在相同素数2