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:
#import resource
import sys
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#import threading
#threading.Thread(target=main).start()
#threading.stack_size(2**26)
#sys.setrecursionlimit(10**6)
mod=(10**9)+7
fact=[1]
for i in range(1,100001):
    fact.append((fact[-1]*i)%mod)
ifact=[0]*100001
ifact[100000]=pow(fact[100000],mod-2,mod)
for i in range(100000,0,-1):
    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import math
import heapq
from random import randint as rn
from Queue import Queue as Q
def find(x):
    if(x!=p[x]):
        p[x]=find(p[x])
    return p[x]
def union(x,y):
    m=find(x)
    n=find(y)
    if(m!=n):
        if(r[m]>r[n]):
            p[n]=m
        elif(r[m]<r[n]):
            p[m]=n
        else:
            p[n]=m
            r[m]+=1
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def GCD(x,y):
    while(y):
        x, y = y, x % y
    return x
def isprime(x):
    if(x==1):
        return False
    elif(x<4):
        return True
    for i in range(2,int(math.sqrt(x))+1):
        if(x%i==0):
            return False
    return True
"""**************************************************************************"""
s=sin()
ans=0
for i in range(3,min(9,len(s)+1)):
    for j in range(0,len(s)-i+1):
        x=s[j:j+i]
        t=0
        for x1 in range(len(x)):
            for k in range(1,4):
                x2=x1+k
                x3=x2+k
                if(x2<len(x) and x3<len(x)):
                    if(x[x1]==x[x2] and x[x1]==x[x3]):
                        ans+=1
                        t=1
                        break
            if(t==1):
                break
for i in range(9,len(s)+1):
    ans+=len(s)+1-i
print ans