#include <bits/stdc++.h>
int dr[] = {2, 2, -2, -2, 1, -1, 1, -1};
int dc[] = {1, -1, 1, -1, 2, 2, -2, -2};
int dr1[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dc1[] = {1, -1, 1, 0, -1, 0, 1, -1};
int dr2[] = {0, 0, 1, -1};
int dc2[] = {1, -1, 0, 0};
using namespace std;
int main() {
  long long int i, j;
  string t;
  vector<long long int> v, v1;
  while (cin >> t) {
    long long int ans = 0;
    long long int max1 = -1;
    for (i = 0; i < t.size(); i++) {
      if (t[i] == '0') {
        if (v.size() == 0) {
          v.push_back(i);
        } else {
          for (j = v.size() - 1; j >= 0; j--) {
            long long int p = v[j];
            long long int k = i - p;
            long long int k1 = i - 2 * k;
            if (k1 <= max1) break;
            if (t[k1] == '0') {
              max1 = k1;
              break;
            }
          }
          v.push_back(i);
        }
      } else if (t[i] == '1') {
        if (v1.size() == 0) {
          v1.push_back(i);
        } else {
          for (j = v1.size() - 1; j >= 0; j--) {
            long long int p = v1[j];
            long long int k = i - p;
            long long int k1 = i - 2 * k;
            if (k1 <= max1) break;
            if (t[k1] == '1') {
              max1 = k1;
              break;
            }
          }
          v1.push_back(i);
        }
      }
      ans += (max1 + 1);
    }
    cout << ans << endl;
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve the following 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.

### Response

```cpp
#include <bits/stdc++.h>
int dr[] = {2, 2, -2, -2, 1, -1, 1, -1};
int dc[] = {1, -1, 1, -1, 2, 2, -2, -2};
int dr1[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dc1[] = {1, -1, 1, 0, -1, 0, 1, -1};
int dr2[] = {0, 0, 1, -1};
int dc2[] = {1, -1, 0, 0};
using namespace std;
int main() {
  long long int i, j;
  string t;
  vector<long long int> v, v1;
  while (cin >> t) {
    long long int ans = 0;
    long long int max1 = -1;
    for (i = 0; i < t.size(); i++) {
      if (t[i] == '0') {
        if (v.size() == 0) {
          v.push_back(i);
        } else {
          for (j = v.size() - 1; j >= 0; j--) {
            long long int p = v[j];
            long long int k = i - p;
            long long int k1 = i - 2 * k;
            if (k1 <= max1) break;
            if (t[k1] == '0') {
              max1 = k1;
              break;
            }
          }
          v.push_back(i);
        }
      } else if (t[i] == '1') {
        if (v1.size() == 0) {
          v1.push_back(i);
        } else {
          for (j = v1.size() - 1; j >= 0; j--) {
            long long int p = v1[j];
            long long int k = i - p;
            long long int k1 = i - 2 * k;
            if (k1 <= max1) break;
            if (t[k1] == '1') {
              max1 = k1;
              break;
            }
          }
          v1.push_back(i);
        }
      }
      ans += (max1 + 1);
    }
    cout << ans << endl;
  }
  return 0;
}

```