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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Set;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        final int LEN = 20;
        List<String> allGood = new ArrayList<>();

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            gen("");
//		Collections.sort(allGood, (u, v) -> (u.length() - v.length()));
//		for (String g : allGood) {
//		    out.println(g);
//        }
//        System.out.println(allGood.get(allGood.size() - 1).length());

            Set<String> set = new HashSet<>(allGood);
            char[] s = in.next().toCharArray();
            int n = s.length;
            long ans = 0;
            for (int i = 0; i < n; i++) {
                StringBuilder cur = new StringBuilder();
                for (int j = i; j < n; j++) {
                    cur.append(s[j]);
                    if (set.contains(cur.toString())) {
                        ans += n - j;
                        break;
                    }
                }
            }
            out.println(ans);
        }

        private void gen(String s) {
            if (isGood(s)) {
                allGood.add(s);
                return;
            }
            if (s.length() >= LEN) {
                return;
            }
            gen(s + "0");
            gen(s + "1");
        }

        private boolean isGood(String s) {
            for (int k = 1; k <= s.length(); k++) {
                for (int i = 0; i + 2 * k < s.length(); i++) {
                    char a = s.charAt(i);
                    char b = s.charAt(i + k);
                    char c = s.charAt(i + 2 * k);
                    if (a == b && b == c) {
                        return true;
                    }
                }
            }
            return false;
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

    }
}