Problem: Toad Rash has a binary string s. A binary string consists only of zeros and ones.

Let n be the length of s.

Rash needs to find the number of such pairs of integers l, r that 1 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ r, and s_x = s_{x+k} = s_{x+2k}.

Find this number of pairs for Rash.

Input

The first line contains the string s (1 ≤ |s| ≤ 300 000), consisting of zeros and ones.

Output

Output one integer: the number of such pairs of integers l, r that 1 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ r, and s_x = s_{x+k} = s_{x+2k}.

Examples

Input


010101


Output


3


Input


11001100


Output


0

Note

In the first example, there are three l, r pairs we need to count: 1, 6; 2, 6; and 1, 5.

In the second example, there are no values x, k for the initial string, so the answer is 0.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long N = 300005;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
  return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
  os << '[';
  for (unsigned long long i = 0; i < a.size(); i++)
    os << a[i] << (i < a.size() - 1 ? ", " : "");
  os << ']';
  return os;
}
string s;
long long a[N];
long long n;
long long pre[N], mark[2][N];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s;
  n = s.size();
  for (long long i = (long long)1; i <= (long long)n; i++)
    a[i] = s[i - 1] - '0';
  memset(pre, -1, sizeof(pre));
  for (long long piv = (long long)1; piv <= (long long)n; piv++) {
    long long lock[2];
    memset(lock, -1, sizeof(lock));
    for (long long j = (long long)piv; j >= (long long)1; j--) {
      long long &it = a[j];
      if (lock[it] == -1)
        lock[it] = j;
      else {
        mark[it][abs(j - lock[it])] = true;
        if (abs(j - lock[it]) % 2 == 0 &&
            mark[it][abs(j - lock[it]) / 2] == true) {
          pre[piv] = j;
          break;
        }
      }
    }
    for (long long j = (long long)max(1LL, pre[piv]); j <= (long long)piv; j++)
      mark[a[j]][abs(j - lock[a[j]])] = false;
  }
  long long mx = -1;
  long long ans = 0;
  for (long long i = (long long)1; i <= (long long)n; i++) {
    mx = max(mx, pre[i]);
    if (mx != -1) ans += mx;
  }
  cout << ans << '\n';
}