According to folklore, the great mathematician Gauss was able to calculate the sum of the first 50 natural numbers in mere seconds. You are given a similar problem, where you have to calculate the sum of the first 'n' natural numbers. The only catch being that the the number 'n' can be really very large. You have to calculate the sum 1+2+...+n for a given value of 'n'. 


Input

The first line consists of a number 't which specifies the number of test cases. 1 ≤ t ≤ 100. 't' lines follow with a number 'n' on each line. 'n' can have upto 20001 digits. 1 ≤ n ≤ (10^20000). 


Output

For each test case, output a number which represents the sum of the first 'n' natural numbers.


Example

Input:
2
3
5
Output:
6
15
Explanation
The sum of the first 3 numbers is 1+2+3 = 6
The sum of the first 5 numbers is 1+2+3+4+5 = 15
import sys
import math
 
# def ndigits(n):
    # return int(math.floor(math.log10(n)) + 1.1)
# 
# m = 10**100
# 
# def tostr(n):
    # if n < m:
        # return str(n)
    # ndig = ndigits(n)
    # botdig = ndig//2
    # mid = 10 ** botdig
    # top = tostr(n // mid)
    # bot = tostr(n % mid)
    # if len(bot) != botdig:
        # return top + '0'*(botdig - len(bot)) + bot
    # return top + bot
 
DIG = 300
MAX = 10**DIG
M2 = (MAX >> 1)
 
def div2(l):
    for i in xrange(len(l)):
        if l[i] & 1 == 1:
            l[i] -= 1
            l[i-1] += MAX/2
        l[i] /= 2
    for i in xrange(len(l)):
        if l[i] < 0:
            l[i] += MAX
            l[i+1] -= 1
    if l[-1] == 0:
        del l[-1]
            
def add1(l):
    i = 0
    while True:
        l[i] += 1
        if l[i] < MAX:
            return
        l[i] = 0
        if i == len(l)-1:
            l.append(1)
            return
        i += 1
 
def multlists(l1, l2):
    rtn = [0] * (len(l1) + len(l2) - 1)
    for i in xrange(len(l1)):
        for j in xrange(len(l2)):
            rtn[i+j] += l1[i] * l2[j]
    # print rtn
    for i in xrange(len(rtn)-1):
        rtn[i+1] += rtn[i] / MAX
        rtn[i] %= MAX
    while rtn[-1] > MAX:
        n = rtn[-1] / MAX
        rtn[-1] %= MAX
        rtn.append(n)
    return rtn
 
def fromstr(s):
    chars = list(reversed(s))
    # print chars
    l = [int(''.join(reversed(chars[i:i+DIG]))) for i in xrange(0, len(chars), DIG)]
    return l
 
def tolist(n):
    l = []
    while n:
        l.append(n % MAX)
        n /= MAX
    return l
 
t = int(sys.stdin.readline())
for _t in xrange(t):
    s = sys.stdin.readline()
    n = fromstr(s.strip())
    # print n
    n1 = list(n)
    add1(n1)
    if n[0] & 1:
        div2(n1)
    else:
        div2(n)
    # print n
    # print n1
    x = multlists(n, n1)
    # print x
    sys.stdout.write('%d' % x.pop())
    FMT = '%%0%dd' % DIG
    for i in reversed(x):
        sys.stdout.write(FMT % i)
    print