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.OutputStream;
import java.util.PriorityQueue;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.io.UncheckedIOException;
import java.util.AbstractCollection;
import java.nio.charset.Charset;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStream;

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

    static class BGoodTriple {
        private static final String[] TOKEN = {
                "000", "111", "01010", "10101", "0**0**0", "1**1**1", "0*1*0*1*0", "1*0*1*0*1",
        };

        public void solve(int testNumber, LightScanner in, LightWriter out) {
            // out.setBoolLabel(LightWriter.BoolLabel.YES_NO_FIRST_UP);
            String s = in.string();
            int n = s.length();
            boolean[] found = new boolean[n];
            PriorityQueue<BGoodTriple.Segment> segments = new PriorityQueue<>();
            TreeSet<Integer> ends = new TreeSet<>();
            Map<Integer, Integer> map = new HashMap<>();
            for (String token : TOKEN) {
                int m = token.length();
                outer:
                for (int i = 0; i <= n - m; i++) {
                    if (found[i]) continue;
                    for (int j = 0; j < m; j++) {
                        if (token.charAt(j) != '*' && s.charAt(i + j) != token.charAt(j)) continue outer;
                    }
                    segments.offer(new BGoodTriple.Segment(i, i + m));
                    ends.add(i + m);
                    map.merge(i + m, 1, Integer::sum);
                    found[i] = true;
                }
            }

            long ans = 0;
            for (int i = 0; i < n; i++) {
                while (!segments.isEmpty() && segments.peek().from < i) {
                    BGoodTriple.Segment invalid = segments.poll();
                    map.merge(invalid.to, -1, Integer::sum);
                    if (map.get(invalid.to) == 0) ends.remove(invalid.to);
                }
                if (!ends.isEmpty()) {
                    ans += n - ends.first() + 1L;
                    //System.out.println("i=" + i + ", " + (n - ends.first() + 1L));
                }
            }
            out.ans(ans).ln();
        }

        private static class Segment implements Comparable<BGoodTriple.Segment> {
            int from;
            int to;

            public Segment(int from, int to) {
                this.from = from;
                this.to = to;
            }

            public String toString() {
                return "Segment{" +
                        "from=" + from +
                        ", to=" + to +
                        '}';
            }

            public int compareTo(BGoodTriple.Segment o) {
                return this.from - o.from;
            }

        }

    }

    static class LightWriter implements AutoCloseable {
        private final Writer out;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter(Writer out) {
            this.out = out;
        }

        public LightWriter(OutputStream out) {
            this(new BufferedWriter(new OutputStreamWriter(out, Charset.defaultCharset())));
        }

        public LightWriter print(char c) {
            try {
                out.write(c);
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter print(String s) {
            try {
                out.write(s, 0, s.length());
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter ans(String s) {
            if (!breaked) {
                print(' ');
            }
            return print(s);
        }

        public LightWriter ans(long l) {
            return ans(Long.toString(l));
        }

        public LightWriter ln() {
            print(System.lineSeparator());
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        public void close() {
            try {
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

    }
}