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 Main{
	public static void main(String[] args) throws Exception{
		new Main().solve();
	}
	void solve() throws Exception{
		InputReader in=new InputReader(System.in);
		PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		char[] s=in.next().toCharArray();
		int n=s.length;
		long ans=0;
		for(int i=0;i<n;i++){
			label:for(int j=i;j<n;j++){
				for(int k=1;j-2*k>=i;k++){
					if(s[j]==s[j-k]&&s[j]==s[j-k*2]){
						ans+=n-j;
						break label;
					}
				}
			}
		}
		out.println(ans);
		out.flush();
	}
	class InputReader{
		StreamTokenizer tokenizer;
		InputReader(InputStream in){
			tokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(in)));
			tokenizer.ordinaryChars(33,126);
			tokenizer.wordChars(33,126);
		}
		public String next() throws IOException{
			tokenizer.nextToken();
			return tokenizer.sval;
		}
		public int nextInt() throws IOException, NumberFormatException{
			return Integer.parseInt(next());
		}
	}
}