## DECSUMS - Sums Decompositions

For any number N, it is possible to decompose N as the sum of one or more positive numbers.

The order of the numbers doesn't matter.

You have to compute the number M of decompositions for each number N.

### Input

The first line of input contains an interger T, the number of testcases (T<20). T testcases follow.

Each testcase consists of a single integer N (1<=N<=120)

### Output

For each testcase you have to output a single line containing the answer for the task.

### Example

Input:2

2

5

Output:2

7

Decompositions for the second testcase:

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

Added by: | legrand |

Date: | 2013-09-13 |

Time limit: | 1s-8s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | general |