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.

debug = False

# represent the string aabbbc as the linked list [[a,2],[b,3],[c,1]]

class element:
	def __init__(self, color, count, left=None, right=None):
		self.color = color
		self.count = count
		self.left = left
		self.right = right

	def __str__(self):
		return '%s%d' % (self.color, self.count)

class linked_list:
	def __init__(self):
		self.first = None
		self.last = None

	def remove(self, node):
		'constant time deletion of any node'
		if node == self.first:
			self.first = node.right
		if node == self.last:
			self.last = node.left
		if node.left:
			node.left.right = node.right
		if node.right:
			node.right.left = node.left

	def append(self, *args):
		'add to end of list'
		new_element = element(*args)
		if self.empty():
			self.first = self.last = new_element
		else:
			new_element.left, self.last.right, self.last = self.last, new_element, new_element

	def empty(self):
		return self.first is None

	def __iter__(self):
		node = self.first
		while node is not None:
			yield node
			node = node.right

	def __str__(self):
		return ' '.join([str(node) for node in self])

def find_min(ll):
	min_value = None
	min_node = None

	for node in ll:
		if min_value is None or node.count < min_value:
			min_node = node
			min_value = node.count
	return min_node

def ops(ll):
	'apply ops and return the number of ops made.'
	min_node = find_min(ll)
	steps = max(1, min_node.count//2)

	# first remove elements

	node = ll.first
	while node != None:
		if node == ll.first or node == ll.last:
			node.count -= steps
		else:
			node.count -= 2*steps # node.count can become negative but that's fine, we're going to remove this below
			if node.count < 0:
				node.count = 0
		node = node.right

	#next merge groups with the same color

	node = ll.first
	while node != None:
		if node.count <= 0:
			# we should remove this node and merge its two neighbors if they have the same color
			ll.remove(node)
			if node.left and node.right and node.left.color == node.right.color:
				node.right.count += node.left.count
				ll.remove(node.left)
		node = node.right

	return steps


def go(s):
	ll = linked_list()

	for c in s:
		if ll.empty():
			ll.append(c, 1)
		elif ll.last.color == c:
			ll.last.count += 1
		else:
			ll.append(c, 1)
	ans = 0
	while ll.first != ll.last:
		if debug:
			print ans, ll
		ans += ops(ll)
	if debug:
		print ans, ll

	return ans


if __name__=='__main__':
	if not debug:
		s = raw_input()
		print go(s)
	else:
		go('bbbaccccccaaaaaccccaaabbcccccccdddddcaaaaaaddddabbbbbbbbbcccaaaabbbbbbbb')
	
