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:
X = [[], ['0', '1'], ['00', '01', '10', '11'], ['001', '010', '011', '100', '101', '110'], ['0010', '0011', '0100', '0101', '0110', '1001', '1010', '1011', '1100', '1101'], ['00100', '00101', '00110', '01001', '01011', '01100', '01101', '10010', '10011', '10100', '10110', '11001', '11010', '11011'], ['001001', '001011', '001100', '001101', '010010', '010011', '010110', '011001', '011010', '011011', '100100', '100101', '100110', '101001', '101100', '101101', '110010', '110011', '110100', '110110'], ['0010011', '0011001', '0011010', '0011011', '0100101', '0101100', '0101101', '0110011', '1001100', '1010010', '1010011', '1011010', '1100100', '1100101', '1100110', '1101100'], ['00110011', '01011010', '01100110', '10011001', '10100101', '11001100']]
s = input()
N = len(s)
ans = (N-1)*(N-2)//2
for i in range(N):
    for j in range(i+3, min(i+9, N+1)):
        if s[i:j] in X[j-i]:
            ans -= 1
print(ans)