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;
template <typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) {
  return os << '(' << pai.first << ' ' << pai.second << ')';
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
  cout << '[';
  for (int i = 0, _i = (((int)(v).size())); i < _i; i++) cout << v[i] << ",";
  cout << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T>
void get_max(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void get_min(T &a, T b) {
  a = min(a, b);
}
int N, M;
string s;
bool test(int l, int r) {
  if (r - l + 1 < 3) return true;
  for (int i = (l + 1), _i = (r); i < _i; i++) {
    vector<int> v1, v2;
    for (int j = i - 1; j >= l; j--)
      if (s[i] == s[j]) v1.push_back(i - j);
    for (int j = i + 1; j <= r; j++)
      if (s[i] == s[j]) v2.push_back(j - i);
    int p1 = 0, p2 = 0;
    while (p1 < ((int)(v1).size()) and p2 < ((int)(v2).size())) {
      if (v1[p1] == v2[p2]) {
        return false;
      } else if (v1[p1] < v2[p2])
        p1++;
      else if (v1[p1] > v2[p2])
        p2++;
    }
  }
  return true;
}
int main(void) {
  iostream::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> s;
  N = ((int)(s).size());
  long long cnt = 0;
  for (int i = 0, _i = (N); i < _i; i++) {
    for (int j = (i), _j = (min(N, i + 12)); j < _j; j++) {
      if (test(i, j)) {
        cnt++;
      }
    }
  }
  cout << (long long)N * (N + 1) / 2 - cnt << '\n';
}