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:
//JDope
import java.util.*;
import java.io.*;
import java.math.*;

public class D{
public static void main(String[] omkar) throws Exception
{
   Set<Integer> a1 = new HashSet<Integer>();
   a1.add(0);
   a1.add(1);
   Set<Integer> a2 = new HashSet<Integer>();
   a2.add(0);
   a2.add(1);
   a2.add(2);
   a2.add(3);
   Set<Integer> a3 = new HashSet<Integer>();
   Set<Integer> a4 = new HashSet<Integer>();
   Set<Integer> a5 = new HashSet<Integer>();
   Set<Integer> a6 = new HashSet<Integer>();
   Set<Integer> a7 = new HashSet<Integer>();
   Set<Integer> a8 = new HashSet<Integer>();

   for(int i = 1; i <= 6; i++)
   {
      a3.add(i);
      if(i > 1)
      {
         a4.add(i);
      }
   }
   for(int i = 9; i <= 13; i++)
   {
      a4.add(i);
   }
   a5.add(4);
a5.add(5);
a5.add(6);
a5.add(9);
a5.add(11);
a5.add(12);
a5.add(13);
a5.add(18);
a5.add(19);
a5.add(20);
a5.add(22);
a5.add(25);
a5.add(26);
a5.add(27);
a6.add(9);
a6.add(11);
a6.add(12);
a6.add(13);
a6.add(18);
a6.add(19);
a6.add(22);
a6.add(25);
a6.add(26);
a6.add(27);
a6.add(36);
a6.add(37);
a6.add(38);
a6.add(41);
a6.add(44);
a6.add(45);
a6.add(50);
a6.add(51);
a6.add(52);
a6.add(54);
a7.add(19);
a7.add(25);
a7.add(26);
a7.add(27);
a7.add(37);
a7.add(44);
a7.add(45);
a7.add(51);
a7.add(76);
a7.add(82);
a7.add(83);
a7.add(90);
a7.add(100);
a7.add(101);
a7.add(102);
a7.add(108);
a8.add(51);
a8.add(90);
a8.add(102);
a8.add(153);
a8.add(165);
a8.add(204);
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   StringBuilder sb = new StringBuilder();
   String s = st.nextToken();
   int[] ones, twos, threes, fours, fives, sixs, sevens, eights, maxR;
   ones = new int[s.length()];
   twos = new int[s.length()];
   threes = new int[s.length()];
   fours = new int[s.length()];
   fives = new int[s.length()];
   sixs = new int[s.length()];
   sevens = new int[s.length()];
   eights = new int[s.length()];
   for(int i = 0; i < s.length(); i++)
   {
      ones[i] = s.charAt(i)-48;
   }
   populate(ones, twos, 2);
   populate(ones, threes, 3);
   populate(ones, fours, 4);
   populate(ones, fives, 5);
   populate(ones, sixs, 6);
   populate(ones, sevens, 7);
   populate(ones, eights, 8);
   maxR = new int[s.length()];
   for(int i = 0; i < ones.length; i++)
   {
      if(i < eights.length-7 && a8.contains(eights[i]))
      {
         maxR[i] = i+7;
      }
      else if(i < sevens.length-6 && a7.contains(sevens[i]))
      {
         maxR[i] = i+6;
      }
      else if(i < sixs.length-5 && a6.contains(sixs[i]))
      {
         maxR[i] = i+5;
      }
      else if(i < fives.length-4 && a5.contains(fives[i]))
      {
         maxR[i] = i+4;
      }
      else if(i < fours.length-3 && a4.contains(fours[i]))
      {
         maxR[i] = i+3;
      }
      else if(i < threes.length-2 && a3.contains(threes[i]))
      {
         maxR[i] = i+2;
      }
      else if(i < twos.length-1)
      {
         maxR[i] = i+1;
      }
      else
      {
         maxR[i] = i;
      }
   }
   long total = 0;
   for(int i = 0; i < maxR.length; i++)
   {
      total += (maxR.length-1) - maxR[i];
   }
   System.out.println(total);
        }
 public static int[] readArr(int N, BufferedReader in, StringTokenizer st) throws Exception
      {
         int[] arr = new int[N];
         st = new StringTokenizer(in.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         return arr;
      }
 public static void populate(int[] arr, int[] arr2, int n)
 {
   if(n > arr.length)
   {
      return;
   }
   for(int i = 0; i < n; i++)
   {
      arr2[0] += arr[i]*(1<<i);
   }
   for(int i = 1; i <= arr.length-n; i++)
   {
      arr2[i] = (arr2[i-1]>>1) + arr[i+n-1]*(1<<(n-1));
   }
 }

}