链接：https://codeforces.ml/contest/1373/problem/C

You are given a string ss 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 infinf denotes infinity, and the characters of the string are numbered from 11 to |s||s|.

You have to calculate the value of the resres after the process ends.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The only lines of each test case contains string ss (1≤|s|≤1061≤|s|≤106) consisting only of characters + and -.

It's guaranteed that sum of |s||s| over all test cases doesn't exceed 106106.

Output

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

Example

input

Copy

3
--+-
---
++--+-

output

Copy

7
9
6

代码：

#include <bits/stdc++.h>
#define ll long long
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
ll n,k,t,l,y,a,b,c,r,s,min1,max1,mod=1e9+7;
map<ll,ll>m;
char x[1000001];
int main()
{
	cin>>t;
	while(t--)
    {
        cin>>x;
        n=strlen(x);
        s=0;
        k=0;
        for(int i=0;i<n-1;i++)
        {
            if(x[i]=='-')
            {
                k--;
                if(k<0)
                {
                    s+=i+1;
                    k++;
                }

            }
            else
                k++;
        }
        if(x[n-1]=='-')
        {
            k--;
            if(k<0)
            {
                s+=n*2;
            }
            else
                s+=n;
        }
        else
            s+=n;
        cout<<s<<endl;


    }
}