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.Arrays;
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.io.FilterInputStream;
import java.io.InputStream;

/**
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DGoodTriple solver = new DGoodTriple();
        solver.solve(1, in, out);
        out.close();
    }

    static class DGoodTriple {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n;
            char[] s = in.scanString().toCharArray();
            n = s.length;
            int pre[] = new int[n];
            Arrays.fill(pre, -1);
            HashSet<Integer> remaining = new HashSet<>();
            for (int i = 0; i < n; i++) remaining.add(i);
            for (int k = 1; k < 10; k++) {
                ArrayList<Integer> del = new ArrayList<>();
                for (int it : remaining) {
                    if (it + (2 * k) >= n) continue;
                    if (s[it] == s[it + k] && s[it + k] == s[it + (2 * k)]) {
                        pre[it + 2 * k] = Math.max(pre[it + 2 * k], it);
                        del.add(it);
                    }
                }
                for (int it : del) remaining.remove(it);
            }

            long ans = 0;
            long l = -1;
            for (int r = 0; r < n; r++) {
                l = Math.max(l, pre[r]);
                ans += (l + 1);
            }
            out.println(ans);

        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public String scanString() {
            int c = scan();
            while (isWhiteSpace(c)) c = scan();
            StringBuilder RESULT = new StringBuilder();
            do {
                RESULT.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return RESULT.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}