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 namespace std;
map<long long, long long> m1, m2;
int main() {
  string s;
  cin >> s;
  long long i, j;
  vector<long long> v1, v2;
  for (i = 0; i < s.size(); i++) {
    if (s[i] == '0') {
      m1[i] = 1;
      v1.push_back(i);
    } else {
      m2[i] = 1;
      v2.push_back(i);
    }
  }
  long long n;
  n = s.size();
  vector<pair<long long, long long>> ans;
  for (i = 0; i < v1.size(); i++) {
    for (j = i + 1; j < v1.size(); j++) {
      long long dif;
      dif = v1[j] - v1[i];
      long long nd;
      nd = v1[j] + dif;
      if (m1.find(nd) != m1.end()) {
        ans.push_back({v1[i] + 1, nd + 1});
        break;
      }
    }
  }
  for (i = 0; i < v2.size(); i++) {
    for (j = i + 1; j < v2.size(); j++) {
      long long dif;
      dif = v2[j] - v2[i];
      long long nd;
      nd = v2[j] + dif;
      if (m2.find(nd) != m2.end()) {
        ans.push_back({v2[i] + 1, nd + 1});
        break;
      }
    }
  }
  sort(ans.begin(), ans.end());
  if (ans.size() == 0) {
    cout << 0 << endl;
    return 0;
  }
  long long n2;
  n2 = ans.size();
  long long arr[n2];
  arr[n2 - 1] = ans[n2 - 1].second;
  long long mini;
  mini = arr[n2 - 1];
  for (i = n2 - 2; i >= 0; i--) {
    arr[i] = min(mini, ans[i].second);
    mini = arr[i];
  }
  long long pre = 0LL;
  long long ans2 = 0LL;
  for (i = 0; i < n2; i++) {
    ans2 += (ans[i].first - pre) * (n - arr[i] + 1);
    pre = ans[i].first;
  }
  cout << ans2 << endl;
}