#include <bits/stdc++.h>
using namespace std;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcount(s);
}
template <class T>
inline T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
string s;
long long n, res;
long long check(long long a, long long b) {
  for (long long l = a, _b = b; l <= _b; l++) {
    for (int h = 1; l + h * 2 <= b; h++) {
      if (s[l] == s[l + h] && s[l] == s[l + 2 * h]) {
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  long long n = s.size();
  s = " " + s;
  for (long long i = 9, _b = n; i <= _b; i++) res += n - i + 1;
  for (long long l = 1, _b = n; l <= _b; l++)
    for (long long i = 0, _b = 7; i <= _b; i++) {
      if (l + i > n) continue;
      res += check(l, l + i);
    }
  cout << res;
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcount(s);
}
template <class T>
inline T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
string s;
long long n, res;
long long check(long long a, long long b) {
  for (long long l = a, _b = b; l <= _b; l++) {
    for (int h = 1; l + h * 2 <= b; h++) {
      if (s[l] == s[l + h] && s[l] == s[l + 2 * h]) {
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  long long n = s.size();
  s = " " + s;
  for (long long i = 9, _b = n; i <= _b; i++) res += n - i + 1;
  for (long long l = 1, _b = n; l <= _b; l++)
    for (long long i = 0, _b = 7; i <= _b; i++) {
      if (l + i > n) continue;
      res += check(l, l + i);
    }
  cout << res;
  return 0;
}

```