You are given a string $s$ consisting only of characters + and -. You perform some process with this string. This process can be described by the following pseudocode: res = 0

for init = 0 to inf

    cur = init

    ok = true

    for i = 1 to |s|

        res = res + 1

        if s[i] == '+'

            cur = cur + 1

        else

            cur = cur - 1

        if cur < 0

            ok = false

            break

    if ok

        break



Note that the $inf$ denotes infinity, and the characters of the string are numbered from $1$ to $|s|$.

You have to calculate the value of the $res$ after the process ends.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only lines of each test case contains string $s$ ($1 \le |s| \le 10^6$) consisting only of characters + and -.

It's guaranteed that sum of $|s|$ over all test cases doesn't exceed $10^6$.


-----Output-----

For each test case print one integer — the value of the $res$ after the process ends.


-----Example-----
Input
3
--+-
---
++--+-

Output
7
9
6

Difficulty: interview

Starter code:

Solutions:
def solve():
    s = input()
    pm = 0
    cur = 0
    ans = len(s)
    for i in range(len(s)):
        if s[i] == '+':
            cur += 1
        else:
            cur -= 1
            if cur < pm:
                pm = cur
                ans += i + 1
    print(ans)
t = int(input())
for _ in range(t):
    solve()

for _ in range(int(input())):
    s = input()
    pref = []
    cur = 0
    for i in s:
        if i == '+':
            cur += 1
        else:
            cur -= 1
        pref.append(cur)
    res, mn = 0, 0
    for i in range(len(pref)):
        if pref[i] < mn:
            mn = pref[i]
            res += i + 1
    print(res + len(s))


import sys
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    s = input()
    n = len(s) - 1
    ru = [0] * (n + 1)
    for i in range(n):
        if s[i] == "+":
            ru[i + 1] = ru[i] + 1
        else:
            ru[i + 1] = ru[i] - 1

    init = -1
    ans = 0
    for i, val in enumerate(ru):
        if val == init:
            ans += i
            init -= 1
    print(ans + n)

def solve():
    s = input()
    min_val = 0
    res = 0
    cur = 0
    for i in range(len(s)):
        if s[i] == '-':
            cur -= 1
        else:
            cur += 1
        if min_val > cur:
            res += (i + 1)
            min_val = cur
    print(res + len(s))


for i in range(int(input())):
    solve()


t=int(input())
for you in range(t):
    res=0
    s=input()
    n=len(s)
    curr=0
    for i in range(n):
        if(s[i]=='+'):
            curr+=1
        else:
            curr-=1
        if(curr<0):
            res+=(i+1)
            curr=0
    print(res+n)


t = int(input())

for _ in range(t):
    s = input()
    
    cur = 0
    m = 0
    res = 0
    for i, c in enumerate(s):
        if c == "+":
            cur += 1
        else:
            cur -= 1
        if cur < m:
            m = cur
            res += i+1
            
    print(res + len(s))
         



tt = int(input())

for loop in range(tt):

    s = input()

    lis = [-1]
    for i in s:
        if i == "-":
            lis.append(lis[-1]+1)
        else:
            lis.append(lis[-1]-1)

    now = -1
    ans = 0
    for i in range(1,len(lis)):
        if lis[i] > now:
            ans += i * (lis[i]-now)
            now = lis[i]

    print(ans + len(s))

    


for _ in range(int(input())):
    s = input()
    cur = 0
    res = 0
    for i in range(len(s)):
        if s[i] == '-':
            cur -= 1
        else:
            cur += 1
        if cur < 0:
            res += i + 1
            cur = 0
    print(res + len(s))

q = int(input())
for _ in range(q):
    s = input()
    n = len(s)
    pref = [0] * n
    pref[0] = 1
    if s[0] == '-':
        pref[0] = -1
    for i in range(1,n):
        pref[i] = pref[i-1] + (1 if s[i] == '+' else -1)
    pierszyminus = [-1]*(n+1)
    for i in range(n):
        j = n-1-i
        if pref[j] < 0:
            pierszyminus[-pref[j]] = j
    wyn = 0
    for i in range(1,n+1):
        wyn += (pierszyminus[i]+1)
    wyn += n
    print(wyn)

import math
for _ in range(int(input())):
    s = list(input())
    l = len(s)
    f = [0 for _ in range(l+1)]
    cp = 0
    cn = 0
    for i in range(l):
        if s[i] == '+':
            cp += 1
        else:
            cn += 1
        if (cn-cp)>0 and f[cn-cp] == 0:
            f[cn-cp] = i+1
    print(sum(f)+l)

for _ in range(int(input())):
    s=input()
    n=len(s)
    data=[0]*n
    for i in range(n):
        if s[i]=="+":
            data[i]=1
        else:
            data[i]=-1
    for i in range(1,n):
        data[i]+=data[i-1]
    data=[-data[i] for i in range(n)]
    for i in range(1,n):
        data[i]=max(data[i],data[i-1])
    #print(data)
    res=0
    val=0
    id=0
    while id<n:
        if data[id]>val:
            res+=(id+1)
            val+=1
        else:
            id+=1
    res+=id
    print(res)


for _ in range(int(input())):
    ar = list(input())
    kek = 0
    lol = 0
    for i in range(len(ar)):
        if ar[i] == '-':
            kek += 1
        else:
            kek -= 1
        if kek > lol:
            lol = kek
    fifi = [-1] * lol
    cur = 0
    for i in range(len(ar)):
        if ar[i] == '-':
            cur += 1
            if cur > 0 and fifi[cur - 1] == -1:
                fifi[cur - 1] = i + 1
        else:
            cur -= 1
    ans = 0
    for elem in fifi:
        ans += elem
    print(len(ar) + ans)


for nt in range(int(input())):
	s = input()
	n = len(s)
	cur = 0
	loop = 0
	ans = 0
	for i in range(n):
		if s[i]=="+":
			cur += 1
		else:
			cur -= 1
		if (cur + loop)<0:
			ans += (i+1)
			loop += 1
			# print (cur,ans,loop)
	print(ans+n)


t=int(input())
for _ in range(t):
    s=input()
    n=len(s)
    ans=0
    grid=[0]*(n+1)
    score=0
    maxmin=0
    for i in range(n):
        if s[i]=='-':
            score-=1
        else:
            score+=1
        maxmin=min(maxmin,score)
    score=0
    for i in range(n):
        if s[i]=='-':
            score-=1
        else:
            score+=1
        if (-1*score-1)>=0:
            if grid[(-1*score)-1]==0:
                grid[(-1*score)-1]=(i+1)
    for i in range(-1*maxmin,n):
        grid[i]=0
    grid[n]=n
    print(sum(grid))