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.*;
import java.util.*;
import java.lang.*;
import java.awt.*;
import java.awt.geom.*;
import java.math.*;
import java.text.*;
import java.math.BigInteger.*;
import java.util.Arrays; 

public class   gsdfgsdfgsd
{
  BufferedReader in;
  StringTokenizer as;
  int nums[],nums2[];
  int a,b;
 
  ArrayList < Integer >  ar = new ArrayList < Integer >();
  ArrayList < Integer >  fi = new ArrayList < Integer >();
  Map<Integer,Integer > map = new HashMap<Integer, Integer>();
  public static void main (String[] args)
  {
    new gsdfgsdfgsd  ();
  }
  
  public int GCD(int a, int b) {
    if (b==0) return a;
    return GCD(b,a%b);
  }
  
  public long solve(int left, int right)
  {
    if(right - left < 16)
    {
      int lp = -1;
      int rp = -1;
      for(int x =left;x<=right;x++)
      {
        for(int x1 = x+1;x1<=right;x1++)
        {
          if(nums[x] == nums[x1] && 2*x1 - x <= right && nums[2*x1 - x] == nums[x])
          {
            lp = x;
            rp = 2*x1 -x;
            break;
          }
        }
        if(lp != -1)
          break;
      }
     // System.out.println(lp + " " + rp + " " + left + " " + right);
      if(lp == -1)
        return 0;
      else
      {
        long temp1 = lp - left + 1;
        long temp2 = right - rp + 1;
        //System.out.println(temp1 + " " + temp2);
        return temp1 * temp2 + solve(left,rp-1) + solve(lp+1,right) - solve(lp+1,rp-1);
      }
    }
    else
    {
      int lp = -1;
      int rp = -1;
      int tleft = (left + right)/2 - 6;
      int tright =  (left + right)/2 + 6;
      for(int x =tleft;x<=tright;x++)
      {
        for(int x1 = x+1;x1<=tright;x1++)
        {
          if(nums[x] == nums[x1] && 2*x1 - x <= right && nums[2*x1 - x] == nums[x])
          {
            lp = x;
            rp = 2*x1 -x;
            break;
          }
        }
        if(lp != -1)
          break;
      }
      if(lp == -1)
        return 0;
      else
      {
        long temp1 = lp - left + 1;
        long temp2 = right - rp + 1;

        return temp1 * temp2 + solve(left,rp-1) + solve(lp+1,right)- solve(lp+1,rp-1);
      }
    }
  }
  
  public gsdfgsdfgsd  ()
  {
    try
    {
      
      in = new BufferedReader (new InputStreamReader (System.in));
      String a = nextLine();
      nums = new int [a.length()];
      
      for(int x = 0;x<a.length();x++)
      {
        if(a.charAt(x) == '1')
          nums[x] = 1;
        else
          nums[x] = 0;
      }
      System.out.println(solve(0,a.length()-1));
      

      
    }
    catch(IOException e)
    {

    }
  }
  
  
  
  
  
  
  
  String next () throws IOException
  {
    while (as == null || !as.hasMoreTokens ())
    {
      as = new StringTokenizer (in.readLine ().trim ());
    }
    
    
    return as.nextToken ();
  }
  
  
  
  long nextLong () throws IOException
  {
    return Long.parseLong (next ());
  }
  
  
  int nextInt () throws IOException
  {
    return Integer.parseInt (next ());
  }
  
  
  double nextDouble () throws IOException
  {
    return Double.parseDouble (next ());
  }
  
  
  String nextLine () throws IOException
  {
    return in.readLine ().trim ();
  }
}