Problem G

Combinatorial Summation

Input: standard input
Output: standard output

Time Limit: 2 seconds

 

   I am sure about your interest with combinations.

Why not put yourself into a test to see your flair?

So here is the problem:

   You are given an integer n(less than 999).

You have to evaluate the expression given at right.

Hope to see you successful with this.

You should count any term as zero which has k < j.

 

Click here if you don't see the image

Input

The first line of input is an integer t(less than 2000). Then follows t lines each of which contain n as described before.

 

Output

There should be one line of output for each input which will be the value of the above expression for the corresponding n.

 

Sample Input

2

3

4

 

Sample Output

7

14

 

---

Problem setter: Mohammad Sajjad Hossain

Special Thanks: Shahriar Manzoor, Member of Elite Problem Setters’ Panel