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.util.*;
import java.io.*;

public class Main {
	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;
	private static long mod = 1000000000 + 7;
	private static long mod1 = 1000000000 + 9;
	private static int MAX=1000001;
	private static int block;
	private static LinkedList<Integer> list[];
	private static boolean Visited[];
	private static int Array[];
	private static int tree[];
	private static int count[];
	private static int result[];
	private static ArrayList<Integer> color[];
	
	private static void soln(){

String s;
int count=0;
int c=0;
s= nextLine();
int x=0,y;
for(int i=0;i<s.length();i++)
{
	if(c==1)
	{
	   y=s.charAt(i)-48;
		x=x+y;
		if(y%3==0 || x%3==0)
			{
				c=0;
				count++;
			}
		else
			c++;
	}
	else if(c==2)
	{
		count++;
		c=0;
	}
	else if(c==0)
	{
		x=s.charAt(i)-48;
		if(x%3==0)
			{
			count++;
			c=0;
			}
		else
			c++;
	}
}
System.out.println(count);


	}
	
	
	
	public static void build(int node, int start, int end,int[] A,int[] B)
	{
	    if(start == end)
	    {
	        // Leaf node will have a single element
	    	if(A[start]+B[start]==2)
	        tree[node] = 1;
	    	else
	    		tree[node] = 0;
	    	if(A[start]+B[start]==0)
	    		Visited[node]=true;
	    	else
	    		Visited[node]=false;
	    }
	    else
	    {
	        int mid = (start + end) / 2;
	        // Recurse on the left child
	        build(2*node, start, mid,A,B);
	        // Recurse on the right child
	        build(2*node+1, mid+1, end,A,B);
	        // Internal node will have the sum of both of its children
	        if(Visited[2*node] || Visited[2*node+1])
	        	Visited[node]=true;
	        if(tree[2*node+1]==1 || ( tree[2*node]==1 && Visited[2*node+1]==false ))
	        	tree[node]=1;
	        else
	        	tree[node]=0;
	    }
	}
	
	public static void update(int node, int start, int end, int idx, int[] A,int[] B)
	{
	    if(start == end)
	    {
	        // Leaf node
	    	if(A[start]+B[start]==2)
		        tree[node] = 1;
		    	else
		    		tree[node] = 0;
		    	if(A[start]+B[start]==0)
		    		Visited[node]=true;
		    	else
		    		Visited[node]=false;
	    }
	    else
	    {
	        int mid = (start + end) / 2;
	        if(start <= idx && idx <= mid)
	        {
	            // If idx is in the left child, recurse on the left child
	            update(2*node, start, mid, idx, A, B);
	        }
	        else
	        {
	            // if idx is in the right child, recurse on the right child
	            update(2*node+1, mid+1, end, idx, A, B);
	        }
	        // Internal node will have the sum of both of its children
	        if(Visited[2*node] || Visited[2*node+1])
	        	Visited[node]=true;
	        if(tree[2*node+1]==1 || ( tree[2*node]==1 && Visited[2*node+1]==false ))
	        	tree[node]=1;
	        else
	        	tree[node]=0;
	    }
	}
	
	public static int query(int node, int start, int end, int l, int r)
	{
	    if(r < start || end < l)
	    {
	        // range represented by a node is completely outside the given range
	        return 2;
	    }
	    if(l <= start && end <= r)
	    {
	        // range represented by a node is completely inside the given range
	        return tree[node];
	    }
	    // range represented by a node is partially inside and partially outside the given range
	    int mid = (start + end) / 2;
	    int p1 = query(2*node, start, mid, l, r);
	    int p2 = query(2*node+1, mid+1, end, l, r);
	    if(p2!=2)
	    {
	    	if(p1+p2>=2)
	    	return 1;
	    	else
	    		return 0;
	    }
	    else
	    {
	    	if(p1==1)
	    		return 2;
	    	else
	    	{
	    		if(Visited[2*node]==false)
	    		return 1;
	    		else
	    			return 0;
	    	}
	    }
	}
	
	public static int dfs(int x,int k)
	{
		int sum=0;
		int size=0;
		Visited[x]=true;
		color[Array[x]].add(x);
		size=color[Array[x]].size();
		if(color[Array[x]].size()>k)
		{
			result[x]=color[Array[x]].get(size-k-1);
		}
		else
		{
			result[x]=-1;
		}
		
		for(Integer a:list[x])
		{
			if(!Visited[a])
			{
				dfs(a,k);
			}
		}
		color[Array[x]].remove(size-1);	
		return 0;
	}

	public static int bfs(int s,int d)
	{
		 //int count[] = new int[101];
		 //count[100]=-1;
		 //boolean Visited[] = new boolean[101];
		
		int c = 0;
		LinkedList<Integer> queue = new LinkedList<Integer>();
		
		Visited[s]=true;
		queue.add(s);
		
		
		while(queue.size()!=0)
		{
			
			s=queue.poll();
			c = count[s]+1;
			for(Integer x: list[s])
			{
				if(Visited[x]!=true)
				{
					Visited[x]=true;
					queue.add(x);
					count[x]=c;
				}
				if(x==d)
					return 0;
			}
		}
		
		return 0;
		
	}
	
	
	
	
	
	
	
	public static class disjointunion
	{
		int parent[],rank[],number[];
		int n;
	public	disjointunion(int n){
			rank = new int[n];
			parent = new int[n];
			number = new int[n];
			this.n=n;
			makeset();
		}
  void makeset()
  {	
	  for(int i=0;i<n;i++)
	  {
		parent[i]=i;
		number[i]=1;
	  }
  }
	int find(int i)
	{
		if(parent[i]!=i)
		{
			parent[i]=find(parent[i]);
		}
			return parent[i];
	}
	void union(int x,int y)
	{
		int xRoot , yRoot;
		xRoot = find(x);
		yRoot = find(y);
		if(xRoot==yRoot)
		return;
		
		if(rank[xRoot]<rank[yRoot])
		{
			parent[xRoot]=yRoot;
			number[yRoot] += number[xRoot];
			number[xRoot]=0;
		}
		if(rank[xRoot]>rank[yRoot])
		{
			parent[yRoot]=xRoot;
			number[xRoot] += number[yRoot];
			number[yRoot]=0;
		}
		if(rank[xRoot]==rank[yRoot])
		{
			parent[xRoot]=yRoot;
			number[yRoot] += number[xRoot];
			number[xRoot]=0;
			rank[yRoot]++;
		}
	}
	}	
		
	public static void main(String[] args) throws Exception 
	{
		new Thread(null,new Runnable()
		{
			@Override
			public void run() 
			{
				InputReader(System.in);
				pw = new PrintWriter(System.out);
				soln();
				pw.close();
			}
		},"1",1<<26).start();
	}

	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[] 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++) 
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c) 
	{
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}
	private static char nextChar() 
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1=(char)c;
		while(!isSpaceChar(c))
			c=read();
		return c1;
	}
	private interface SpaceCharFilter 
	{
		public boolean isSpaceChar(int ch);
	}
	
	
}