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.Scanner;

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

    static class TaskB {
        final int THRESHOLD = 9;

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            try {
                String str = in.next();
                long res = 0;
                for (int i = 0; i < str.length(); i++) {
                    if (i + THRESHOLD <= str.length()) {
                        res += str.length() - i - THRESHOLD + 1;
                    }
                    for (int j = 1; j < THRESHOLD && i + j <= str.length(); j++) {
                        if (has(str.substring(i, i + j))) {
                            res++;
                        }
                    }
                }
                out.println(res);
            } catch (Exception e) {
            }
        }

        boolean has(String str) {
            for (int k = 1; k <= str.length(); k++) {
                for (int i = 0; i + 2 * k < str.length(); i++) {
                    if (str.charAt(i + k) == str.charAt(i) && str.charAt(i + 2 * k) == str.charAt(i)) {
                        return true;
                    }
                }
            }
            return false;
        }

    }
}