#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;
long long fastpower(long long x, long long n) {
  if (n == 0)
    return 1;
  else if (n % 2 == 0)
    return fastpower((x * x), n / 2);
  else
    return (x * fastpower((x * x), (n - 1) / 2));
}
long long negativepow(long long base, long long expo, long long m) {
  if (m == 1) return 0;
  long long ans = 1, y = base % m;
  while (expo > 0) {
    if (expo & 1) ans = ((ans)*y) % m;
    y = (y * y) % m;
    if (y < 0) y += m;
    expo = expo >> 1;
  }
  if (ans < 0) {
    ans = (m - abs(ans) % m);
    return ans;
  }
  return ans % m;
}
long long GCD(long long A, long long B) {
  if (B == 0)
    return A;
  else
    return GCD(B, A % B);
}
bool vowl(char c) {
  return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
void sieve(long long N) {
  bool isPrime[N + 1];
  for (long long i = 0; i <= N; ++i) {
    isPrime[i] = true;
  }
  isPrime[0] = false;
  isPrime[1] = false;
  for (long long i = 2; i * i <= N; ++i) {
    if (isPrime[i] == true) {
      for (long long j = i * i; j <= N; j += i) isPrime[j] = false;
    }
  }
}
bool isPrime(long long n) {
  if (n <= 1) return 0;
  if (n == 2 || n == 3) return 1;
  if (n % 2 == 0 || n % 3 == 0)
    return 0;
  else {
    for (long long i = 5; i * i <= n; i += 6) {
      if (n % i == 0 || n % (i + 2) == 0) return 0;
    }
    return 1;
  }
}
map<long long, long long> factor(long long n) {
  map<long long, long long> pm;
  long long i;
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        pm[i]++;
        n = n / i;
      }
    }
  }
  if (n > 1) pm[n]++;
  return pm;
}
void printDivisors(long long n) {
  vector<long long> v;
  for (long long i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        v.push_back(i);
      else {
        v.push_back(i);
        v.push_back(n / i);
      }
    }
  }
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second < b.second);
}
void print(vector<long long> v) {
  for (auto it : v) cout << it << " ";
  cout << "\n";
}
long long count_one(long long n) {
  long long count = 0;
  while (n) {
    n = n & (n - 1);
    count++;
  }
  return count;
}
long long sz(string s) { return s.length(); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long sum = 0;
    long long index = -1;
    long long cnt = 0;
    for (long long i = 0; i < s.length(); i++) {
      if (s[i] == '-')
        sum--;
      else
        sum++;
      if (sum < 0) {
        sum = 0;
        cnt += i + 1;
      }
    }
    cout << cnt + s.length() << "\n";
  }
  return 0;
}

### Prompt

Your task is to create a Cpp solution 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;
const int M = 1e9 + 7;
long long fastpower(long long x, long long n) {
  if (n == 0)
    return 1;
  else if (n % 2 == 0)
    return fastpower((x * x), n / 2);
  else
    return (x * fastpower((x * x), (n - 1) / 2));
}
long long negativepow(long long base, long long expo, long long m) {
  if (m == 1) return 0;
  long long ans = 1, y = base % m;
  while (expo > 0) {
    if (expo & 1) ans = ((ans)*y) % m;
    y = (y * y) % m;
    if (y < 0) y += m;
    expo = expo >> 1;
  }
  if (ans < 0) {
    ans = (m - abs(ans) % m);
    return ans;
  }
  return ans % m;
}
long long GCD(long long A, long long B) {
  if (B == 0)
    return A;
  else
    return GCD(B, A % B);
}
bool vowl(char c) {
  return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
void sieve(long long N) {
  bool isPrime[N + 1];
  for (long long i = 0; i <= N; ++i) {
    isPrime[i] = true;
  }
  isPrime[0] = false;
  isPrime[1] = false;
  for (long long i = 2; i * i <= N; ++i) {
    if (isPrime[i] == true) {
      for (long long j = i * i; j <= N; j += i) isPrime[j] = false;
    }
  }
}
bool isPrime(long long n) {
  if (n <= 1) return 0;
  if (n == 2 || n == 3) return 1;
  if (n % 2 == 0 || n % 3 == 0)
    return 0;
  else {
    for (long long i = 5; i * i <= n; i += 6) {
      if (n % i == 0 || n % (i + 2) == 0) return 0;
    }
    return 1;
  }
}
map<long long, long long> factor(long long n) {
  map<long long, long long> pm;
  long long i;
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        pm[i]++;
        n = n / i;
      }
    }
  }
  if (n > 1) pm[n]++;
  return pm;
}
void printDivisors(long long n) {
  vector<long long> v;
  for (long long i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        v.push_back(i);
      else {
        v.push_back(i);
        v.push_back(n / i);
      }
    }
  }
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second < b.second);
}
void print(vector<long long> v) {
  for (auto it : v) cout << it << " ";
  cout << "\n";
}
long long count_one(long long n) {
  long long count = 0;
  while (n) {
    n = n & (n - 1);
    count++;
  }
  return count;
}
long long sz(string s) { return s.length(); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long sum = 0;
    long long index = -1;
    long long cnt = 0;
    for (long long i = 0; i < s.length(); i++) {
      if (s[i] == '-')
        sum--;
      else
        sum++;
      if (sum < 0) {
        sum = 0;
        cnt += i + 1;
      }
    }
    cout << cnt + s.length() << "\n";
  }
  return 0;
}

```