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;
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
template <class T>
inline void chmax(T &a, const T &b) {
  if ((a) < (b)) (a) = (b);
}
template <class T>
inline void chmin(T &a, const T &b) {
  if ((a) > (b)) (a) = (b);
}
template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast {
  Fast() {
    std::cin.tie(0);
    ios::sync_with_stdio(false);
  }
} fast;
long long solve() {
  string s;
  cin >> s;
  long long n = ((long long)(s).size());
  if (n <= 2) {
    cout << 0 << endl;
    return 0;
  }
  long long res = 0;
  long long sum = 0;
  long long r = 2;
  for (long long l = 0; l < n; ++l) {
    auto isok = [&]() {
      if (r - l <= 1) return true;
      for (long long k = (long long)(1); k < (long long)(20); ++k) {
        if (r - 2 * k < l) break;
        if (s[r] == s[r - k] && s[r - k] == s[r - 2 * k]) {
          return false;
        }
      }
      return true;
    };
    while (r < n && isok()) {
      ++r;
    }
    res += n - r;
    if (r == l) ++r;
  }
  cout << res << endl;
  return 0;
}
signed main() {
  solve();
  return 0;
}