#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
long long st[4 * 200001];
long long binExp(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % 1000000007;
    x = (x * x) % 1000000007;
    n >>= 1;
  }
  return res;
}
long long modInv(long long i) { return binExp(i, 1000000007 - 2); }
void build(long long s, long long e, long long i, long long a[]) {
  if (s == e) {
    st[i] = a[s];
    return;
  }
  long long mid = s + (e - s) / 2;
  build(s, mid, 2 * i + 1, a);
  build(mid + 1, e, 2 * i + 2, a);
  st[i] = st[2 * i + 1] + st[2 * i + 2];
}
long long query(long long s, long long e, long long i, long long a[],
                long long l, long long r) {
  if (s > e || l > r) return 0;
  if (s >= l && e <= r) return st[i];
  if (s > r || e < l) return 0;
  long long mid = s + (e - s) / 2;
  return query(s, mid, 2 * i + 1, a, l, r) +
         query(mid + 1, e, 2 * i + 2, a, l, r);
}
long long update(long long s, long long e, long long i, long long pos,
                 long long val) {
  if (s == e && s == pos) {
    st[i] = val;
    return 0;
  }
  if (s > pos || e < pos) return 0;
  long long mid = s + (e - s) / 2;
  update(s, mid, 2 * i + 1, pos, val);
  update(mid + 1, e, 2 * i + 2, pos, val);
  st[i] = st[2 * i + 1] + st[2 * i + 2];
}
long long parent[200000], size[200000];
long long find_set(long long v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void make_set(long long v) {
  parent[v] = v;
  size[v] = 1;
}
void union_sets(long long a, long long b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (size[a] < size[b]) swap(a, b);
    parent[b] = a;
    size[a] += size[b];
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long c = 0;
    map<long long, long long> m;
    for (long long i = 0; i < s.length(); i++) {
      if (s[i] == '+') {
        c++;
      } else
        c--;
      if (m[c] == 0) m[c] = i + 1;
    }
    long long ans = 0;
    for (long long i = 0; i < s.length() + 1; i++) {
      if (m[-1 * i - 1] == 0) {
        ans += s.length();
        break;
      }
      ans += m[-1 * i - 1];
    }
    cout << ans << endl;
  }
}

### Prompt

Please create a solution in cpp to the following problem:

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 ≤ t ≤ 1000) — the number of test cases.

The only lines of each test case contains string s (1 ≤ |s| ≤ 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
long long st[4 * 200001];
long long binExp(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % 1000000007;
    x = (x * x) % 1000000007;
    n >>= 1;
  }
  return res;
}
long long modInv(long long i) { return binExp(i, 1000000007 - 2); }
void build(long long s, long long e, long long i, long long a[]) {
  if (s == e) {
    st[i] = a[s];
    return;
  }
  long long mid = s + (e - s) / 2;
  build(s, mid, 2 * i + 1, a);
  build(mid + 1, e, 2 * i + 2, a);
  st[i] = st[2 * i + 1] + st[2 * i + 2];
}
long long query(long long s, long long e, long long i, long long a[],
                long long l, long long r) {
  if (s > e || l > r) return 0;
  if (s >= l && e <= r) return st[i];
  if (s > r || e < l) return 0;
  long long mid = s + (e - s) / 2;
  return query(s, mid, 2 * i + 1, a, l, r) +
         query(mid + 1, e, 2 * i + 2, a, l, r);
}
long long update(long long s, long long e, long long i, long long pos,
                 long long val) {
  if (s == e && s == pos) {
    st[i] = val;
    return 0;
  }
  if (s > pos || e < pos) return 0;
  long long mid = s + (e - s) / 2;
  update(s, mid, 2 * i + 1, pos, val);
  update(mid + 1, e, 2 * i + 2, pos, val);
  st[i] = st[2 * i + 1] + st[2 * i + 2];
}
long long parent[200000], size[200000];
long long find_set(long long v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void make_set(long long v) {
  parent[v] = v;
  size[v] = 1;
}
void union_sets(long long a, long long b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (size[a] < size[b]) swap(a, b);
    parent[b] = a;
    size[a] += size[b];
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long c = 0;
    map<long long, long long> m;
    for (long long i = 0; i < s.length(); i++) {
      if (s[i] == '+') {
        c++;
      } else
        c--;
      if (m[c] == 0) m[c] = i + 1;
    }
    long long ans = 0;
    for (long long i = 0; i < s.length() + 1; i++) {
      if (m[-1 * i - 1] == 0) {
        ans += s.length();
        break;
      }
      ans += m[-1 * i - 1];
    }
    cout << ans << endl;
  }
}

```