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;
using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
auto& errStream = cerr;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
void dmpr(decltype(cerrDummy)& os) { os << endl; }
template <class T, class... Args>
void dmpr(decltype(cerrDummy)& os, const T& t, const Args&... args) {
  os << t << " ";
  dmpr(os, args...);
}
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (ll i = ll(0); i < ll((ll)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "(";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << ")";
}
ll read() {
  ll i;
  scanf("%lld", &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, ll suc = 1) {
  printf("%lld", x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static ll bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "Yes" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "No" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
constexpr ll TEN(ll n) { return n == 0 ? 1 : TEN(n - 1) * 10; }
template <class T>
vector<T> uni(const vector<T>& vv) {
  auto v(vv);
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  return v;
}
template <class T>
void mkuni(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
bool inc(ll a, ll b, ll c) { return a <= b && b <= c; }
VV<bool> table;
void Init() {
  const ll B = 10;
  table.resize(B + 1);
  for (ll n = ll(1); n < ll(B + 1); n++) {
    table[n].resize(1 << n);
    for (ll bit = ll(0); bit < ll(1 << n); bit++) {
      string s;
      for (ll i = ll(0); i < ll(n); i++) s += '0' + ((bit >> i) & 1);
      bool f = false;
      for (ll x = ll(0); x < ll(n); x++)
        for (ll z = x + 2; z < n; z += 2) {
          ll y = (x + z) / 2;
          if (s[x] == s[y] && s[y] == s[z]) f = true;
        }
      if (!f) dmpr(cerrDummy, n, s);
      table[n][bit] = f;
    }
  }
}
signed main() {
  Init();
  string s = readString();
  ll n = s.size();
  ll ans = 0;
  for (ll i = ll(0); i < ll(n); i++) {
    ll j = i, cur = 0;
    while (1) {
      if (j == n) {
        j++;
        break;
      }
      cur = cur * 2 + s[j++] - '0';
      if (table[j - i][cur]) break;
    }
    ans += n + 1 - j;
  }
  print(ans);
}