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 PYTHON):

Solution:
from collections import deque, namedtuple
import random
import time

seed = int(time.time())
random.seed(seed)

def solve_slow(s):
    n = len(s)
    acc = 0
    for l in range(n-2):
        for r in range(l+2, n):
            ok = False
            for x in range(l, r-1):
                for k in range(1, (r-x)//2+1):
                    if s[x] == s[x+k] and s[x] == s[x+2*k]:
                        ok = True
                        break
                if ok:
                    break
            acc += ok
    return acc

def solve(s):
    n = len(s)
    acc = 0
    prev_l = -1
    for l in range(n):
        for r in range(l+2, n, 2):
            if s[l] == s[(l+r)//2] and s[l] == s[r]:
                acc += (n - r)*(l-prev_l)
                prev_l = l
                break
    return acc

def solve_tutorial(s):
    n = len(s)
    acc = 0
    vl = [n for _ in range(n+1)]
    for i in range(n-1, -1, -1):
        vl[i] = vl[i+1]
        k = 1
        while i + 2*k < vl[i]:
            if s[i] == s[i+k] and s[i+k] == s[i+2*k]:
                vl[i] = i + 2*k
            k += 1
        acc += n - vl[i]
    return acc

def main():
    s = raw_input().strip()
    if False:
        ex = solve_slow(s)
        ac = solve(s)
        assert ex == ac, "expected %s, got %s" % (ex, ac)
    print solve_tutorial(s)

if '__main__'==__name__:
    main()