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.*;

public class triple {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
//		int n=9;
//		T:for(int i=0;i<1<<n;i++) {
//			String x=Integer.toBinaryString(i);
//			while(x.length()<n) x="0"+x;
//			for(int j=0;j<n;j++) {
//				for(int k=1;k<n;k++) {
//					if(j+2*k>=n) continue;
//					if(x.charAt(j)==x.charAt(j+k)&&x.charAt(j+k)==x.charAt(j+2*k)) {
//						continue T;
//					}
//				}
//			}
//			System.out.println("NO PATTERN "+x);
//		}
		long good=0L;
//		StringBuilder x=new StringBuilder();
//		for(int i=0;i<300000;i++) x.append("0");
		char[] a=scan.next().toCharArray();
//		char[] a=x.toString().toCharArray();
		int n=a.length;
		for(int i=0;i<n;i++) {
			for(int j=i;j<n&&j<i+8;j++) {
				if(pat(a,i,j)) {
//					System.out.println(i+" "+j);
					good++;
				}
			}
		}
		if(n>=9) {
			long dif=n-8;
			good+=dif*(dif+1)/2;
		}
		System.out.println(good);
	}
	public static boolean pat(char[] a, int l, int r) {
		for(int j=l;j<r;j++) {
			for(int k=1;k<=r-l;k++) {
				if(j+2*k>r) continue;
				if(a[j]==a[j+k]&&a[j+k]==a[j+2*k]) {
					return true;
				}
			}
		}
		return false;
	}
}
/*
1100110011
*/