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;
default_random_engine generator;
uniform_int_distribution<int> distribution(1, INT_MAX);
vector<vector<long long> > one(int sz) {
  vector<vector<long long> > ret;
  ret.resize(sz);
  for (int i = 0; i < ret.size(); i++) {
    ret[i].resize(sz);
    for (int j = 0; j < ret.size(); j++) {
      ret[i][j] = (i == j);
    }
  }
  return ret;
}
vector<vector<long long> > mult(vector<vector<long long> > a,
                                vector<vector<long long> > b) {
  vector<vector<long long> > ret;
  ret.resize(a.size());
  for (int i = 0; i < ret.size(); i++) {
    ret[i].resize(a.size());
    for (int j = 0; j < ret.size(); j++) {
      ret[i][j] = 0;
    }
  }
  for (int k = 0; k < ret.size(); k++) {
    for (int i = 0; i < a.size(); i++) {
      for (int j = 0; j < b.size(); j++) {
        ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]);
        ret[i][j] %= 998244353;
      }
    }
  }
  return ret;
}
vector<vector<long long> > pw(vector<vector<long long> > a, long long b) {
  if (b == 0) return one((int)a.size());
  if (b % 2) return mult(a, pw(a, b - 1));
  return pw(mult(a, a), b / 2);
}
long long my_rand(long long a = 0, long long b = INT_MAX) {
  return a + distribution(generator) % b;
}
inline int mul(int a, int b) { return int(a * 1ll * b % 998244353); }
inline int norm(int a) {
  if (a >= 998244353) a -= 998244353;
  if (a < 0) a += 998244353;
  return a;
}
inline int binPow(int a, int k) {
  int ans = 1;
  while (k > 0) {
    if (k & 1) ans = mul(ans, a);
    a = mul(a, a);
    k >>= 1;
  }
  return ans;
}
inline int subtract(int a, int b) { return norm(a - b); }
inline int sum(int a, int b) { return int((a + b) % 998244353); }
inline int inv(int a) { return binPow(a, 998244353 - 2); }
long long ceil_int(long long a, long long b) { return a / b + (a % b != 0); }
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
int main() {
  generator.seed(chrono::system_clock::now().time_since_epoch().count());
  cin.sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  long long n = s.length();
  long long ans = n * (n - 1) / 2;
  for (long long l = 0; l < n; l++) {
    for (long long r = l + 1; r < n; r++) {
      if (r - l >= 9) break;
      int ok = 0;
      for (long long i = l; i <= r; i++) {
        for (long long j = 1; i + 2 * j <= r; j++) {
          if (s[i] == s[i + j] && s[i] == s[i + 2 * j]) {
            ok = 1;
            break;
          }
          if (ok) break;
        }
      }
      if (!ok) ans--;
    }
  }
  cout << ans;
  return 0;
}