Problem: Polycarp likes numbers that are divisible by 3.

He has a huge number s. Polycarp wants to cut from it the maximum number of numbers that are divisible by 3. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after m such cuts, there will be m+1 parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by 3.

For example, if the original number is s=3121, then Polycarp can cut it into three parts with two cuts: 3|1|21. As a result, he will get two numbers that are divisible by 3.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by 3 that Polycarp can obtain?

Input

The first line of the input contains a positive integer s. The number of digits of the number s is between 1 and 2⋅10^5, inclusive. The first (leftmost) digit is not equal to 0.

Output

Print the maximum number of numbers divisible by 3 that Polycarp can get by making vertical cuts in the given number s.

Examples

Input

3121


Output

2


Input

6


Output

1


Input

1000000000000000000000000000000000


Output

33


Input

201920181


Output

4

Note

In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by 3.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and 33 digits 0. Each of the 33 digits 0 forms a number that is divisible by 3.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers 0, 9, 201 and 81 are divisible by 3.

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.math.*;
import java.util.*;
import java.util.Map.Entry;


                    public class CODE2{
                    	private static InputStream stream;
                        private static byte[] buf = new byte[1024];
                        private static int curChar;
                        private static int numChars;
                        private static SpaceCharFilter filter;
                        private static PrintWriter pw;
                        static int BIT[];
                        public final static int INF = (int) 1E9;
                        static ArrayList<Integer> adj[];
                        static boolean Visited[];
                        static HashSet<Integer> exc;
                        static long oddsum[]=new long[1000001];
                        static long co=0,ans=0;
                        static int parent[];
                        static int size[],color[],res[],k;
                        static ArrayList<Integer> al[];
                        static long MOD = (long)1e9 + 7;
                        static int[] levl,dist;
                        static int[] eat;
                        static int nm = 1000007;
                        static boolean divisor[];
                        static int[] phi;
                        static int mod = (int)1e9 + 7;
                        static HashSet<Integer> div ;
                     static double maxvector = 1.5 * (1e6);
                        
                        public static void solve(){
                        	   
                        	char c[] = nextLine().toCharArray();
                        	
                        	int digit[] = new int[c.length];
                        	
                        	for(int i=0;i<c.length;i++)
                        		digit[i] = (c[i] - '0')%3;
                        	int n = c.length; 
                        	int sum =0;
                        	//int prev = 0;
                        	int res =0;
                        	int lc=0;
                        	int rc =0;
                        	for(int i=0;i<n;i++)
                        	{
                        		if(digit[i]==0)
                        		{
                        			res++;
                        			sum=0;
                        			lc =0;
                        			rc =0;
                        		}
                        		else
                        		{
                        			if(digit[i]==2)
                        			{
                        				if(lc!=0 || rc>=2)
                        				{
                        					lc =0;rc=0;
                        					res++;
                        				}
                        				else
                        					rc++;
                        			}
                        			else if(digit[i]==1)
                        			{
                        				if(rc!=0 || lc>=2)
                        				{
                        					res++;
                        					lc =0;
                        					rc =0;
                        					
                        				}
                        				else
                        					lc++;
                        			}
                        		}
                        	}
                        	
                        			pw.println(res);
                        	
                  
                    	}	
public static void main(String args[]) {
    InputReader(System.in);
    pw = new PrintWriter(System.out); 
    new Thread(null ,new Runnable(){
       public void run(){
           try{
               solve();
               
               pw.close();
           } catch(Exception e){
               e.printStackTrace();
           }
       }
   },"1",1<<26).start();
   }
    static StringBuilder sb;
    public static void test(){
         sb=new StringBuilder();
        int t=nextInt();
        while(t-->0){
            
            solve();
           
        }
        pw.println(sb);
    }
    public static long pow(long n, long p,long mod) {
        if(p==0)
            return 1;
        if(p==1)
            return n%mod;
        if(p%2==0){
            long temp=pow(n, p/2,mod);
        return (temp*temp)%mod;
        }else{
                 long temp=pow(n,p/2,mod);
                 temp=(temp*temp)%mod;
                 return(temp*n)%mod;
                 
        }
    }
    public static long pow(long n, long p) {
        if(p==0)
            return 1;
        if(p==1)
            return n;
        if(p%2==0){
            long temp=pow(n, p/2);
        return (temp*temp);
        }else{
                 long temp=pow(n,p/2);
                 temp=(temp*temp);
                 return(temp*n);
                 
        }
    }
    public static long gcd(long x, long y) {
        if (x == 0)
            return y;
        else
            return gcd( y % x,x);
    }    
    
    public static boolean isPrime(int n) {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }
        
      private static void buildgraph(int n){
            adj=new ArrayList[n+1];
            Visited=new boolean[n+1];
            levl=new int[n+1];
            
            for(int i=0;i<=n;i++){
                adj[i]=new ArrayList<Integer>();
            
            }


        }
 
       
      
   static void sprime()
   {
	   spf=new int[nm+1];
	   for(int i=2;i<nm;i++)
	   {
		   if(spf[i]!=0)
			   continue;
		   for(int j=i;j<nm;j+=i)
		   {
			   spf[j] = i;
		   }
	   }
   }
   
   
   
    
        static void toposort(int i)
        {
        	Visited[i] = true;
        	
        	for(int j : adj[i])
        	{
        		if(!Visited[j])
        			toposort(j);
        	}
        	
        }
        static void comp(int n)
        {
        	for(int i=1;i<=Math.sqrt(n);i++)
        	{
        		if(n%i==0)
        		{
        			if(i==n/i)
        				div.add(i);
        			else
        			{
        				div.add(i);
        				div.add(n/i);
        			}
        		}
        	}
        }
        static void calculatephi()
        {
        	int end = (int)1e6 + 5;
        	for(int i=1;i<end;i++)
        		phi[i] = i;
        	for(int i=2;i<end;i++)
        	{
        		if(phi[i]==i)
        		{
        			phi[i] = i - 1;
        			for(int j=2 * i;j<end;j=j+i)
            		{
            			phi[j] = (phi[j]/i) * (i-1);
            		}
        		}
        		
        	}
        	
        }
        static void randomize( long  arr[], int n)
        {
            Random r = new Random();
            for (int i = n-1; i > 0; i--) {
                int j = r.nextInt(i);
                long  temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }                 
        static class pa implements Comparator<Integer>
    	{
    		

    		
    		public int compare(Integer a,Integer b)
    		{
    			return b-a;
    					
    		}
    	}
        static class node implements Comparable<node>
    	{
    		long r;long i;
    		
    		node(long r,long i)
    		{
    			this.r = r;
    			this.i = i; 
    		}
    		
    		public int compareTo(node other)
    		{
    			return Long.compare(this.r,other.r);
    					
    		}
    	}
       
        
     /*   static void BITupdate(int x,int val)
        {
        	while(x<=n)
        	{
        		BIT[x]+=val;
        		x+= x & -x;
        	}
        }*/
     /*   static void update(int x,long val)
        {
      
        	val=val%MOD;
        	while(x<=n)
        	{
        		// System.out.println(x);
        	BIT[x]=(BIT[x]+val)%MOD;
        	x+=(x & -x);
        	}
        //	System.out.println("dfd");
        }*/
        static int BITsum(int x)
        		{
        	int sum=0;
        	while(x>0)
        	{
        		sum+=BIT[x];
        		x-= (x & -x);
        	}
        		return sum;
        		}
  /*      static long sum(int x)
        {
        	long sum=0;
        	while(x>0)
        	{
        		sum=(sum+BIT[x])%MOD;
        		x-=x & -x;
        	}
        	return sum;
        }*/
        static boolean union(int x,int y)
        {
        	int xr=find(x);
        	int yr=find(y);
        	if(xr==yr)
        		return false;
        	if(size[xr]<size[yr])
        	{
        		size[yr]+=size[xr];
        		parent[xr]=yr;
        	}
        	else
        	{
        		size[xr]+=size[yr];
        		parent[yr]=xr;
        		
        	}
        	return true;
        	
        }
        static int  find(int x)
        {
        	if(parent[x]==x)
        		return x;
        	else
        	{
        		parent[x]=find(parent[x]);
        		return parent[x];
        	}
        	
        }
        public static class Edge implements Comparable<Edge>
        {
        	long x;int i;
			public Edge(long x,int i) 
			{
				this.x = x;
				this.i = i;
				//this.s = s;
			}
			public int hashCode() 
			{
				return Objects.hash();
			}
			public int compareTo(Edge other) 
			{
				return Long.compare(this.x,other.x);
				
			}
			
        }
       
        static int col[];
   
static int no_vert=0;

    public static String reverseString(String s) {
        StringBuilder sb = new StringBuilder(s);
        sb.reverse();
        return (sb.toString());
    }
    
  



                  static int indeg[];
               /* private static void kahn(int n){
                    
                    PriorityQueue<Integer> q=new PriorityQueue<Integer>();
                    for(int i=1;i<=n;i++){
                        if(indeg[i]==0){
                            q.add(i);
                        }
                    }
                    while(!q.isEmpty()){
                        int top=q.poll();
                        st.push(top);
                        for(Node i:adj[top]){
                            indeg[i.to]--;
                            if(indeg[i.to]==0){
                                q.add(i.to);
                            }
                        }
                    }
                }
                    
                    static int state=1;
                    static long no_exc=0,no_vert=0;
                  static Stack<Integer> st;
                  static HashSet<Integer> inset;
                   private static void topo(int curr){
                        
                        Visited[curr]=true;
                        inset.add(curr);
                        for(int x:adj[curr]){
                            if(adj[x].contains(curr) || inset.contains(x)){
                                state=0;
                                return;
                            }
                            if(state==0)
                                return;
                            
                        }
                        st.push(curr);
                        
                        inset.remove(curr);
                    }*/
                    static HashSet<Integer> hs;
                   
                 
                     static boolean prime[];
                    static int spf[];
                    public static void sieve(int n){
                        prime=new boolean[n+1];
                        spf=new int[n+1];
                        
                        Arrays.fill(spf, 1);
                        Arrays.fill(prime, true);
                    prime[1]=false;
                        spf[2]=2;
                        
                    
                    for(int i=2;i*i<=n;i++){
                        if(prime[i]){
                            spf[i]=i;
                            for(int j=2*i;j<=n;j+=i){
                                
                                prime[j]=false;
                           
                            }
                        }
                    }
                    
                        
                    }
                     
                    // To Get Input
// Some Buffer Methods
 
                    
                    public static void InputReader(InputStream stream1) {
                        stream = stream1;
                    }
 
                    private static boolean isWhitespace(int c) {
                        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
                    }
 
                    private static boolean isEndOfLine(int c) {
                        return c == '\n' || c == '\r' || c == -1;
                    }
 
                    private static int read() {
                        if (numChars == -1)
                            throw new InputMismatchException();
                        if (curChar >= numChars) {
                            curChar = 0;
                            try {
                                numChars = stream.read(buf);
                            } catch (IOException e) {
                                throw new InputMismatchException();
                            }
                            if (numChars <= 0)
                                return -1;
                        }
                        return buf[curChar++];
                    }
 
                    private static int nextInt() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        int sgn = 1;
                        if (c == '-') {
        sgn = -1;
        c = read();
    }
    int res = 0;
    do {
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
                            c = read();
                        } while (!isSpaceChar(c));
                        return res * sgn;
                    }
 
                    private static long nextLong() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        int sgn = 1;
                        if (c == '-') {
        sgn = -1;
        c = read();
    }
    long res = 0;
    do {
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
                            c = read();
                        } while (!isSpaceChar(c));
                        return res * sgn;
                    }
 
                    private static String nextToken() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        StringBuilder res = new StringBuilder();
                        do {
                            res.appendCodePoint(c);
                            c = read();
                        } while (!isSpaceChar(c));
                        return res.toString();
                    }
 
                    private static String nextLine() {
                        int c = read();
                        while (isSpaceChar(c))
                            c = read();
                        StringBuilder res = new StringBuilder();
                        do {
                            res.appendCodePoint(c);
                            c = read();
                        } while (!isEndOfLine(c));
                        return res.toString();
                    }
 
                    private static int[] nextIntArray(int n) {
                        int[] arr = new int[n];
                        for (int i = 0; i < n; i++) {
                            arr[i] = nextInt();
                        }
                        return arr;
                    }
 
                    private static long[][] next2dArray(int n, int m) {
                        long[][] arr = new long[n][m];
                        for (int i = 0; i < n; i++) {
                            for (int j = 0; j < m; j++) {
                                arr[i][j] = nextLong();
                            }
                        }
                        return arr;
                    }
                    private static char[][] nextCharArray(int n,int m){
                        char [][]c=new char[n][m];
                        for(int i=0;i<n;i++){
                            String s=nextLine();
                            for(int j=0;j<s.length();j++){
                                c[i][j]=s.charAt(j);
                            }
                        }
                        return c;
                    }
 
                    private static long[] nextLongArray(int n) {
                        long[] arr = new long[n];
                        for (int i = 0; i < n; i++) {
                            arr[i] = nextLong();
                        }
                        return arr;
                    }
 
                    private static void pArray(int[] arr) {
                        for (int i = 0; i < arr.length; i++) {
                            pw.print(arr[i] + " ");
                        }
                        pw.println();
                        return;
                    }
 
                    private static void pArray(long[] arr) {
                        for (int i = 0; i < arr.length; i++) {
                            pw.print(arr[i] + " ");
                        }
                        pw.println();
                        return;
                    }
 
                    private static void pArray(boolean[] arr) {
                        for (int i = 0; i < arr.length; i++) {
                            pw.print(arr[i] + " ");
                        }
                        pw.println();
                        return;
                    }
 
                    private static boolean isSpaceChar(int c) {
                        if (filter != null)
                            return filter.isSpaceChar(c);
                        return isWhitespace(c);
                    }
 
                    private interface SpaceCharFilter {
                        public boolean isSpaceChar(int ch);
                    }
                    

}