Let G(S) denote the sum of the elements of set S and F(n) be the sum of G(s) for all subsets of the set consisting of the first n natural numbers. 

For example, F(3) = (1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24.



Given n, calculate F(1) + F(2) + ... + F(n).


Input

The first line contains the number of test cases T ( ≤ 1000). Each of the next T lines contains an integer n. (1 ≤ n ≤ 1000000000).

Output

Output T lines, one corresponding to each test case. Since the answers can get very big, output the answer modulo 8388608

Example

Input:
3
1
2
3
Output:
1
7
31
# summing subsets - resno5.py

ans=[0]*23
#f = []

for k in range(1,23):
    fk = (k*(k+1)/2 * 2**(k-1) ) % 8388608
    #f.append(fk)
    ans[k] = (ans[k-1] + fk) % 8388608  # answer is sum of fk's

# 8388608 = 2^23,  so f[23] = 23*24/2 * 2^22 %23 =0, and
#          all higher k's have factor of 2^23 or more

# sum(f[n]) 1..k = sum(f[n])1..23 for k>

t = int(raw_input())

for iter in range(t):
    n = int(raw_input())
    if n>22:
        n=22
    print ans[n]