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
#!/usr/bin/python
"Solve the Summing Subsets problem at CodeChef"
MODVALUE = 8388608  # 2 ** 23
import sys
def main():
 testcases = int(raw_input())
 for testcase in xrange(testcases):
  n = int(raw_input())
  print s(n)
def f(n):
 """empirically, using pencil and paper, you can come up with this formula:

    f(n) = sum(xrange(n + 1)) * (2 ** (n - 1))
 """
 total = 0
 for i in xrange(n + 1):
  total = (total + i) % MODVALUE
 for i in xrange(1, n):
  total = (total + total) % MODVALUE
 #print >>sys.stderr, 'f(%d) = %d' % (n, total)
 return total
def s(n):
 """any number over 22 produces a number f(n) with no bits below 2 ** 23 set

    therefore all s(n>22) is MODVALUE - 1
 """
 if (n > 22): return MODVALUE - 1
 total = 0
 for i in xrange(1, n + 1):
  total = (f(i) + total) % MODVALUE
 return total
main()