You are given a set of points on a straight line. Each point has a color assigned to it. For point a, its neighbors are the points which don't have any other points between them and a. Each point has at most two neighbors - one from the left and one from the right.

You perform a sequence of operations on this set of points. In one operation, you delete all points which have a neighbor point of a different color than the point itself. Points are deleted simultaneously, i.e. first you decide which points have to be deleted and then delete them. After that you can perform the next operation etc. If an operation would not delete any points, you can't perform it.

How many operations will you need to perform until the next operation does not have any points to delete?

Input

Input contains a single string of lowercase English letters 'a'-'z'. The letters give the points' colors in the order in which they are arranged on the line: the first letter gives the color of the leftmost point, the second gives the color of the second point from the left etc.

The number of the points is between 1 and 106.

Output

Output one line containing an integer - the number of operations which can be performed on the given set of points until there are no more points to delete.

Examples

Input

aabb


Output

2


Input

aabcaa


Output

1

Note

In the first test case, the first operation will delete two middle points and leave points "ab", which will be deleted with the second operation. There will be no points left to apply the third operation to.

In the second test case, the first operation will delete the four points in the middle, leaving points "aa". None of them have neighbors of other colors, so the second operation can't be applied.
import java.io.* ;
import java.util.* ;
import java.text.* ;
import java.math.* ;
import static java.lang.Math.min ;
import static java.lang.Math.max ;
public class Codeshefcode{
	public static void main(String[] args) throws IOException{
		Solver Machine = new Solver() ;
		Machine.Solve() ;
		Machine.Finish() ;
		// new Thread(null,new Runnable(){
		// 	public void run(){
		// 		Solver Machine = new Solver() ;
		// 		try{
		// 			Machine.Solve() ;
		// 			Machine.Finish() ;
		// 		}catch(Exception e){
		// 			e.printStackTrace() ;
		// 			System.out.flush() ;
		// 			System.exit(-1) ;
		// 		}catch(Error e){
		// 			e.printStackTrace() ;
		// 			System.out.flush() ;
		// 			System.exit(-1) ;
		// 		}
		// 	}
		// },"Solver",1l<<27).start() ;
	}
}
class Mod{
	static long mod=1000000007 ;
	static long d(long a,long b){ return (a*MI(b))%mod ; }
	static long m(long a,long b){ return (a*b)%mod ; }
	static private long MI(long a){ return pow(a,mod-2) ; }
	static long pow(long a,long b){
		if(b<0) return pow(MI(a),-b) ;
		long val=a ; long ans=1 ;
		while(b!=0){
			if((b&1)==1) ans = (ans*val)%mod ; 
			val = (val*val)%mod ; 
			b/=2 ;
		}
		return ans ;
	}	
}
class pair implements Comparable<pair>{
	int x ; int y ;  
	pair(int x,int y){ this.x=x ; this.y=y ;} 
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}
class Node{
	int sz ; char cr ;
	Node(int _sz,char _cr){
		sz = _sz ; cr = _cr ;
	}
}
class Solver{
	Reader ip = new Reader(System.in) ;	  
	PrintWriter op = new PrintWriter(System.out) ;
	public void Solve() throws IOException{
		char c[] = (ip.s()+"A").toCharArray() ;
		int n = c.length-1 ;
		int ct=1 ;
		mylist ls = new mylist() ;
		for(int i=0 ; i<n ; i++){
			if(c[i]!=c[i+1]){
				Node nd = new Node(ct,c[i]) ;
				ls.add(nd) ;
				ct=1 ;
			}else
				ct++ ;
		}
		int opr=0 ;
		while(ls.size()>1){
			op.flush() ;
			opr++ ;
			for(int i=0 ; i<ls.size() ; i++)
				if(i==0 || i==(ls.size()-1))
					ls.get(i).sz-- ;
				else
					ls.get(i).sz-=2 ;
			mylist nls = new mylist() ;
			char prev = 'A' ;
			for(Node itr : ls){
				if(itr.sz>0){
					if(itr.cr==prev)
						nls.get(nls.size()-1).sz+=itr.sz ;
					else{
						nls.add(itr) ;
					}
					prev = itr.cr ;
				}
			}
			ls = nls ;
		}
		pln(opr) ;
	}
	void Finish(){
		op.flush();
		op.close();
	}
	void p(Object o){
		op.print(o) ;
	}
	void pln(Object o){
		op.println(o) ;
	}		
}
class mylist extends ArrayList<Node>{}
class myset extends TreeSet<Integer>{}
class mystack extends Stack<Integer>{}
class mymap extends TreeMap<Long,Integer>{}
class Reader {
	BufferedReader reader;
	StringTokenizer tokenizer;
	Reader(InputStream input) {
		reader = new BufferedReader(
					new InputStreamReader(input) );
		tokenizer = new StringTokenizer("") ;
	}
	String s() throws IOException {
		while (!tokenizer.hasMoreTokens()){
			tokenizer = new StringTokenizer(
			reader.readLine()) ;
		}
		return tokenizer.nextToken();
	}
	int i() throws IOException {
		return Integer.parseInt(s()) ;
	}
	long l() throws IOException{
		return Long.parseLong(s()) ;
	}
	double d() throws IOException {
		return Double.parseDouble(s()) ;
	}
}
