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>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-8;
inline long long read() {
  char c;
  long long out = 0, f = 1;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) {
    out = (out << 3) + (out << 1) + c - '0';
  }
  return out * f;
}
inline void read(long long &x) {
  char c;
  long long f = 1;
  x = 0;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) {
    x = (x << 3) + (x << 1) + c - '0';
  }
  x *= f;
}
void write(long long x) {
  if (x < 0) {
    putchar('-');
    write(-x);
    return;
  }
  if (x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
void wts(long long x) {
  write(x);
  putchar(' ');
}
void wtb(long long x) {
  write(x);
  putchar('\n');
}
template <typename... Args>
void read(long long &x, Args &...args) {
  read(x);
  read(args...);
}
template <typename... Args>
void wts(long long x, Args... args) {
  wts(x);
  wts(args...);
}
template <typename... Args>
void wtb(long long x, Args... args) {
  wtb(x);
  wtb(args...);
}
template <class T>
inline bool up(T &x, const T &y) {
  return x < y ? x = y, 1 : 0;
}
template <class T>
inline bool dn(T &x, const T &y) {
  return x > y ? x = y, 1 : 0;
}
const long long N = 300010;
const long long mod = 1000000007;
char s[N];
long long n, ans, mn[N];
signed main() {
  long long l, r, k;
  scanf("%s", s + 1);
  n = strlen(s + 1);
  ans = n * (n + 1) / 2;
  for (l = 1; l <= n + 1; ++l) mn[l] = n + 1;
  for (k = 100; k >= 1; --k) {
    for (l = 1; l <= n; ++l) {
      if (l + 2 * k <= n && s[l] == s[l + k] && s[l] == s[l + 2 * k]) {
        mn[l] = l + 2 * k;
      }
    }
  }
  for (l = n; l >= 1; --l) {
    mn[l] = min(mn[l], mn[l + 1]);
    ans -= mn[l] - l;
  }
  cout << ans;
  return 0;
}