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 islammohsen
 */
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);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public int solve(String sub) {
            int ret = 100000000;
            for (int i = 1; i <= 10; i++) {
                for (int j = 0; j < sub.length(); j++) {
                    if (j + 2 * i >= sub.length())
                        break;
                    if (sub.charAt(j) == sub.charAt(j + i) && sub.charAt(j) == sub.charAt(j + 2 * i))
                        ret = Math.min(ret, j + 2 * i);
                }
            }
            if (ret > 10)
                return 0;
            else
                return sub.length() - ret;
        }

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            String s;
            s = in.next();
            int n = s.length();
            long ans = 0;
            for (int i = 0; i < n; i++) {
                int lastIdx = i + 8;
                if (lastIdx < n)
                    ans += n - lastIdx;
                String sub = s.substring(i, Math.min(lastIdx, n));
                ans += solve(sub);
            }
            out.print(ans);
        }

    }
}