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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer; 
					  
					
					public class temp4 {
						static class FastReader 
					    { 
					        BufferedReader br; 
					        StringTokenizer st; 
					  
					        public FastReader() 
					        { 
					            br = new BufferedReader(new
					                     InputStreamReader(System.in)); 
					        } 
					  
					        String next() 
					        { 
					            while (st == null || !st.hasMoreElements()) 
					            { 
					                try
					                { 
					                    st = new StringTokenizer(br.readLine()); 
					                } 
					                catch (IOException  e) 
					                { 
					                    e.printStackTrace(); 
					                } 
					            } 
					            return st.nextToken(); 
					        } 
					  
					        int nextInt() 
					        { 
					            return Integer.parseInt(next()); 
					        } 
					  
					        long nextLong() 
					        { 
					            return Long.parseLong(next()); 
					        } 
					  
					        double nextDouble() 
					        { 
					            return Double.parseDouble(next()); 
					        } 
					  
					        String nextLine() 
					        { 
					            String str = ""; 
					            try
					            { 
					                str = br.readLine(); 
					            } 
					            catch (IOException e) 
					            { 
					                e.printStackTrace(); 
					            } 
					            return str; 
					        } 
					    } 
						
					/*	static class Reader 
					    { 
					        final private int BUFFER_SIZE = 1 << 16; 
					        private DataInputStream din; 
					        private byte[] buffer; 
					        private int bufferPointer, bytesRead; 
					  
					        public Reader() 
					        { 
					            din = new DataInputStream(System.in); 
					            buffer = new byte[BUFFER_SIZE]; 
					            bufferPointer = bytesRead = 0; 
					        } 
					  
					        public Reader(String file_name) throws IOException 
					        { 
					            din = new DataInputStream(new FileInputStream(file_name)); 
					            buffer = new byte[BUFFER_SIZE]; 
					            bufferPointer = bytesRead = 0; 
					        } 
					  
					        public String readLine() throws IOException 
					        { 
					            byte[] buf = new byte[64]; // line length 
					            int cnt = 0, c; 
					            while ((c = read()) != -1) 
					            { 
					                if (c == '\n') 
					                    break; 
					                buf[cnt++] = (byte) c; 
					            } 
					            return new String(buf, 0, cnt); 
					        } 
					  
					        public int nextInt() throws IOException 
					        { 
					            int ret = 0; 
					            byte c = read(); 
					            while (c <= ' ') 
					                c = read(); 
					            boolean neg = (c == '-'); 
					            if (neg) 
					                c = read(); 
					            do
					            { 
					                ret = ret * 10 + c - '0'; 
					            }  while ((c = read()) >= '0' && c <= '9'); 
					  
					            if (neg) 
					                return -ret; 
					            return ret; 
					        } 
					  
					        public long nextLong() throws IOException 
					        { 
					            long ret = 0; 
					            byte c = read(); 
					            while (c <= ' ') 
					                c = read(); 
					            boolean neg = (c == '-'); 
					            if (neg) 
					                c = read(); 
					            do { 
					                ret = ret * 10 + c - '0'; 
					            } 
					            while ((c = read()) >= '0' && c <= '9'); 
					            if (neg) 
					                return -ret; 
					            return ret; 
					        } 
					  
					        public double nextDouble() throws IOException 
					        { 
					            double ret = 0, div = 1; 
					            byte c = read(); 
					            while (c <= ' ') 
					                c = read(); 
					            boolean neg = (c == '-'); 
					            if (neg) 
					                c = read(); 
					  
					            do { 
					                ret = ret * 10 + c - '0'; 
					            } 
					            while ((c = read()) >= '0' && c <= '9'); 
					  
					            if (c == '.') 
					            { 
					                while ((c = read()) >= '0' && c <= '9') 
					                { 
					                    ret += (c - '0') / (div *= 10); 
					                } 
					            } 
					  
					            if (neg) 
					                return -ret; 
					            return ret; 
					        } 
					  
					        private void fillBuffer() throws IOException 
					        { 
					            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
					            if (bytesRead == -1) 
					                buffer[0] = -1; 
					        } 
					  
					        private byte read() throws IOException 
					        { 
					            if (bufferPointer == bytesRead) 
					                fillBuffer(); 
					            return buffer[bufferPointer++]; 
					        } 
					  
					        public void close() throws IOException 
					        { 
					            if (din == null) 
					                return; 
					            din.close(); 
					        } 
					    } */
						static class Print
					{
						    private final BufferedWriter bw;
						    public Print()
						    {
						        bw=new BufferedWriter(new OutputStreamWriter(System.out));
						    }
					    public void print(String str)throws IOException
						    {
						        bw.append(str);
						    }
						    public void println(String str)throws IOException
						    {
						        print(str);
						        bw.append("\n");
						    }
						    public void close()throws IOException
						    {
						        bw.close();
						    }} 
							
							
							
							public static void main(String[] args) throws IOException {			
								FastReader scn=new FastReader();
								Print pr=new Print();
								String s=scn.next();
								long n=s.length(),l=0,r=0,k=0,flag=0,ans=0;
								for(l=0;l<n;l++){
									for(r=l;r<n;r++){
										flag=0;
										for(k=1;r-2*k>=l;k++){
											if(s.charAt((int) r)==s.charAt((int) (r-k))&&s.charAt((int)r)==s.charAt((int)(r-2*k))){
												ans+=n-r;
												flag=1;break;
											}
										}
										if(flag==1)break;
									}
								}
								pr.println(ans+"");
								pr.close();
								
							}

							public static class node{
								int a;
								int b;
								public node(int a,int b){
									this.a=a;this.b=b;
								}
							}
							
					}