We all learned the factorial of N is N!=1 * 2 * 3 * … * N(if N>=0).Base on the factorial, we give the parts definition of N>=0 of the DOUBLE FACTORIAL N!!.
Give you a 0 <= N <=18, please calculate the answer S = 0!! + 1!! + 2!! + … N!!
Input
The first Line is a Number T, means there is T cases.
Next T line, each line is a number N(0 <= N <= 18)
Output
For each case, output a line, include the answer number S.