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

Solution:
import sys
input = sys.stdin.readline

S=input().strip()
L=len(S)

ANS1=[0]*(L+10)
ANS2=[0]*(L+10)
ANS3=[0]*(L+10)

for i in range(L-2):
    if S[i]==S[i+1]==S[i+2]:
        ANS1[i]=1

for i in range(L-4):
    if S[i]==S[i+2]==S[i+4]:
        ANS2[i]=1

for i in range(L-6):
    if S[i]==S[i+3]==S[i+6]:
        ANS3[i]=1

SCORE=0

for i in range(L):
    if ANS1[i]==1:
        SCORE+=max(0,L-i-2)
    elif ANS1[i+1]==1:
        SCORE+=max(0,L-i-3)
    elif ANS1[i+2]==1:
        SCORE+=max(0,L-i-4)

    elif ANS2[i]==1:
        SCORE+=max(0,L-i-4)
    elif ANS2[i+1]==1:
        SCORE+=max(0,L-i-5)

        
    elif ANS1[i+3]==1:
        SCORE+=max(0,L-i-5)


        
        
    elif ANS1[i+4]==1:
        SCORE+=max(0,L-i-6)
    elif ANS2[i+2]==1:
        SCORE+=max(0,L-i-6)
    elif ANS3[i]==1:
        SCORE+=max(0,L-i-6)
        
    elif ANS1[i+5]==1:
        SCORE+=max(0,L-i-7)
    elif ANS2[i+3]==1:
        SCORE+=max(0,L-i-7)
    elif ANS3[i+1]==1:
        SCORE+=max(0,L-i-7)
     

    else:
        SCORE+=max(0,L-i-8)

    #print(SCORE)

print(SCORE)