PROGRAMMING:Scheme number of natural number splitting
Given a natural number n, it is required to divide n into several positive integers, and the number participating in the addition operation can be repeated. Similar to the "natural number splitting problem", it also needs to satisfy the non repetition of the scheme.
The so-called repeatability of splitting method is determined as follows: given $$n = a_ 1 + a_ 2 + ... a_{ M1} $$and $$n = b_ 1 + b_ 2 + ...b_{ M2} $$represents two splitting methods of integer n. For $$\ forall a_ i, b_ J \ \ GEQ 1 $$, let set $$a = \ {a}_ i| 1 \leq i \leq m_ 1\}, B= \{b_ j| 1 \leq j \leq m_ 2\}$$。 If the set $$a = B $$, then the two splitting methods are repeated.
For example, 6 = 3 + 2 and 6 = 2 + 3 are repeated splitting methods.
How many kinds of splits do you need to satisfy now?
###Input format:
The first natural integer T represents the number of test data groups,
After t line, each line has a natural number n, (1 < n < = 4000)
**Note: the scale of this question is 4000. Is backtracking still suitable? Think carefully about how to design the algorithm**
**It is suggested to learn the related knowledge completely by yourself**
###Output format:
T line, each line outputs an integer, which represents the number of splitting schemes. The result is modulo 2147483648.
###Input example:
Here is a set of inputs. For example:
```in
two
six
seven
```
###Output example:
The corresponding output is given here. For example:
```out
eleven
fifteen
```
answer：If there is no answer, please comment
The so-called repeatability of splitting method is determined as follows: given $$n = a_ 1 + a_ 2 + ... a_{ M1} $$and $$n = b_ 1 + b_ 2 + ...b_{ M2} $$represents two splitting methods of integer n. For $$\ forall a_ i, b_ J \ \ GEQ 1 $$, let set $$a = \ {a}_ i| 1 \leq i \leq m_ 1\}, B= \{b_ j| 1 \leq j \leq m_ 2\}$$。 If the set $$a = B $$, then the two splitting methods are repeated.
For example, 6 = 3 + 2 and 6 = 2 + 3 are repeated splitting methods.
How many kinds of splits do you need to satisfy now?
###Input format:
The first natural integer T represents the number of test data groups,
After t line, each line has a natural number n, (1 < n < = 4000)
**Note: the scale of this question is 4000. Is backtracking still suitable? Think carefully about how to design the algorithm**
**It is suggested to learn the related knowledge completely by yourself**
###Output format:
T line, each line outputs an integer, which represents the number of splitting schemes. The result is modulo 2147483648.
###Input example:
Here is a set of inputs. For example:
```in
two
six
seven
```
###Output example:
The corresponding output is given here. For example:
```out
eleven
fifteen
```
answer：If there is no answer, please comment