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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public final class Triple
{
	public static void main(String[] args) throws IOException
	{
		Reader.init(System.in);
		String str = Reader.next();
		char[] st = str.toCharArray();
		int n = st.length;
		long sum = 0;
		int r = n;
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = 1; (i + 2 * j) < r; j++)
			{
				if (st[i] == st[i + j] && st[i + j] == st[i + 2 * j])
				{
					r = (i + 2 * j);
				}
			}
			sum += n - r;
		}
		System.out.println(sum);
	}
}

class Reader
{
	static BufferedReader reader;
	static StringTokenizer tokenizer;
	
	/** call this method to initialize reader for InputStream */
	static void init(InputStream input)
	{
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}
	
	/** get next word */
	static String next() throws IOException
	{
		while (!tokenizer.hasMoreTokens())
		{
			// TODO add check for eof if necessary
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
	
	static int nextInt() throws IOException
	{
		return Integer.parseInt(next());
	}
	
	static double nextDouble() throws IOException
	{
		return Double.parseDouble(next());
	}
	
	static long nextLong() throws IOException
	{
		return Long.parseLong(next());
	}
}