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.util.*;
import java.io.*;
public class EdA {

	public static void main(String[] args) throws Exception{
		long num = 998244353;

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);

//	 		String input2 = bf.readLine().trim();
	 	String input = bf.readLine().trim();
	 	int n = input.length();
	 	int[] array = new int[n];
	 	for(int j =0 ;j<n;j++)
	 		array[j] = input.charAt(j)-'0';
	 	long prod = 0;
	 	long curr = 0;
	 	for(int j = 0;j<n;j++){
	 		boolean found = true;
	 		for(int k = Math.max(0,  j-5);k<j;k++)
	 			if (2*k-j >= 0 && array[2*k-j] == array[k] && array[k] == array[j])
	 				curr = Math.max(curr, 2*k-j+1);
	 		prod+=curr;
	 		
	 	}
	 	out.println(prod);
	 	
 		out.close();
 		
 	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is