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

/**
 * Created on 5/11/2017.
 */
public class B {
    Scanner sc;
    PrintWriter pw;

    void run() throws FileNotFoundException {
        // sc = new Scanner(new File("D.txt"));
        sc = new Scanner(System.in);
        pw = new PrintWriter(System.out);

//        int[] a = new int[100];
//        int k = 9;
//        int count = 0;
//        for (int ii = 0; ii < (1 << k); ii++) {
//            for (int i = 0; i < k; i++) {
//                a[i] = (ii / (1 << i)) % 2;
//            }
//
//            boolean good = false;
//            for (int i = 0; i < k; i++) {
//                for (int s = 1; i + 2 * s < k; s++) {
//                    if (a[i] == a[i + s] && a[i] == a[i + 2 * s]) {
//                        good = true;
//                        break;
//                    }
//                }
//            }
//            if (!good) {
//                for (int i = 0; i < k; i++) {
//                    System.out.print(a[i] + " ");
//                }
//                System.out.println();
//                count++;
////                System.exit(0);
//            }
//        }
//        System.out.println(count + " bad possibilities");
//        System.exit(0);

        String str = sc.next();
        char[] a = str.toCharArray();
        long n = a.length;
        long nBad = 0;
        for (int i = 0; i < n; i++) {
            for (int len = 1; len < 9; len++) {
                if (i + len > n) {
                    break;
                }

                boolean hasTriplet = false;
                for (int i0 = i; i0 < i + len && !hasTriplet; i0++) {
                    for (int s = 1; i0 + 2 * s < i + len; s++) {
                        if (a[i0] == a[i0 + s] && a[i0] == a[i0 + 2 * s]) {
                            hasTriplet = true;
                            break;
                        }
                    }
                }

                if (!hasTriplet) {
                    nBad++;
                }
            }
        }

        long nGood = n * (n + 1) / 2 - nBad;
        pw.println(nGood);
        pw.close();
    }

    public static void main(String[] args) throws FileNotFoundException {
        B sol = new B();
        sol.run();
    }
}