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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Andy Phan
 */
public class p1169d {
    public static void main(String[] args) {
        JS in = new JS();
        String s = in.next();
        int last = -1;
        long tot = 0;
        for(int i = 0; i < s.length(); i++) {
            last = Math.max(last, i-9);
            for(int j = 1; j <= 5; j++) {
                if(i-j-j < 0) break;
                if(s.charAt(i) == s.charAt(i-j) && s.charAt(i) == s.charAt(i-j-j)) {
                    last = Math.max(last, i-j-j);
                    break;
                }
            }
            tot += last+1;
        }
        System.out.println(tot);
    }static class JS {

        public int BS = 1 << 16;
        public char NC = (char) 0;
        byte[] buf = new byte[BS];
        int bId = 0, size = 0;
        char c = NC;
        double num = 1;
        BufferedInputStream in;

        public JS() {
            in = new BufferedInputStream(System.in, BS);
        }

        public JS(String s) throws FileNotFoundException {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        }

        public char nextChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) {
                    return NC;
                }
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            num = 1;
            boolean neg = false;
            if (c == NC) {
                c = nextChar();
            }
            for (; (c < '0' || c > '9'); c = nextChar()) {
                if (c == '-') {
                    neg = true;
                }
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = nextChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                num *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + (cur < 0 ? -1 * nextLong() / num : nextLong() / num);
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) {
                c = nextChar();
            }
            while (c > 32) {
                res.append(c);
                c = nextChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) {
                c = nextChar();
            }
            while (c != '\n') {
                res.append(c);
                c = nextChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) {
                return true;
            }
            while (true) {
                c = nextChar();
                if (c == NC) {
                    return false;
                } else if (c > 32) {
                    return true;
                }
            }
        }
    }
}