Problem Description:
A pyramid has been constructed using bricks. All these bricks are made of gold. However the quality of gold varies from brick to brick. The value of the bricks has been marked equivalent to nCr. Where n is the nth row of the pyramid from the top, and r is the number of the brick in that row (Both n and r start from 0). One day an invader comes and takes away all the outermost bricks of the pyramid. This disrupts the outermost shield and now some weird things happen.
1. All the rows in which the outermost golden bricks(after the invasion) have value which is not a prime number, magically disappear.
2. The value of the outermost brick can neither be a prime number nor a composite number. So now, the value of the bricks in each row gets magically divided by the value of the outermost brick.
Find out the total amount magically lost.

Input:

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of Bricks.
 

Output:

For each test case, print the net amount that gets magically lost.


Constraints:
30 Points :
1 ≤ T ≤ 30
1 ≤ N ≤ 125

70 Points :
1 ≤ T ≤ 50
1 ≤ N ≤ 500



Example:
Sample Input:
2
10
21

Sample Output:
5
43
from math import sqrt
 
 
def disp(A):
    j = 0
    for i in A:
        print j, i
        j += 1
    print 
 
def Asum(A):
    s = 0L
    for i in A:
        s += sum(i)
    return long(s)
 
def solve(N):
    N = sqrt(1 + 8*N) - 1
    N /= 2
    N = int(N)
#    print N
    A = [[0] * (i + 1) for i in xrange(N)]
    A[0][0] = 1
    for i in xrange(1, N):
        A[i][0] = A[i][i] = 1
        for j in xrange(1, i):
            A[i][j] = A[i-1][j-1] + A[i-1][j]
#    disp(A)
    removeoutermost(A, N)
    A = A[2:]
#    disp(A)
    prev = Asum(A)
    A = step2(A)
#    disp(A)
    step3(A)
#    disp(A)
    print prev - Asum(A)
    
 
def removeoutermost(A, N):
    for i in xrange(0, N):
        A[i] = A[i][1:-1]
 
def is_prime(N):
    if (N == 1):
        return False
    for i in xrange(2, N):
        if N % i == 0:
            return False
    return True
 
def step2(A):
    B = [x for x in A if is_prime(x[0])]
    return B
 
def step3(A):
    for i in xrange(len(A)):
        div = A[i][0]
        for j in xrange(len(A[i])):
            A[i][j] /= div
 
t = input()
for i in xrange(t):
    n = input()
    solve(n)