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.util.*;
import java.io.*;

public class B562 {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        String s = sc.next(); int n = s.length();
        int [] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = s.charAt(i) - '0';
        int [] left = new int[n];
        Arrays.fill(left, -1);
        Set<Integer> set = new HashSet<>();
        for (int i = 2; i <= n - 1; i++) set.add(i);
        for (int k = 1; k <= Math.min(20, (n - 1) / 2); k++) {
            ArrayList<Integer> remove = new ArrayList<>();
            for (Integer i: set) {
                int first = a[i - 2 * k];
                int middle = a[i - k];
                int last = a[i];
                if (first == middle && middle == last) {
                    left[i] = Math.max(left[i], i - 2 * k);
                    remove.add(i);
                }
            }
            for (Integer x: remove) set.remove(x);
            set.remove(2 * k);
            set.remove(2 * k + 1);
        }
        int curMax = -1;
        for (int i = 0; i < n; i++) {
            left[i] = Math.max(left[i], curMax);
            curMax = Math.max(curMax, left[i]);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (left[i] != -1) {
                ans = (ans + (long) left[i] + 1);
            }
        }
        out.println(ans);
        out.close();
    }


    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }


    }

}