Chef likes trees a lot. Today he has an infinte full binary tree (each node has exactly two childs) with special properties.
Chef's tree has the following special properties :

Each node of the tree is either colored red or black.
Root of the tree is black intially.
Both childs of a red colored node are black and both childs of a black colored node are red.


The root of the tree is labelled as 1. For a node labelled v, it's left child is labelled as 2*v and it's right child is labelled as 2*v+1.


Chef wants to fulfill Q queries on this tree. Each query belongs to any of the following three types:


Qi 	   Change color of all red colored nodes to black and all black colored nodes to red.
Qb x y  Count the number of black colored nodes on the path from node x to node y (both inclusive).
Qr x y  Count the number of red colored nodes on the path from node x to node y (both inclusive).

Help chef accomplishing this task.

Input
First line of the input contains an integer Q denoting the number of queries. Next Q lines of the input contain Q queries (one per line). Each query belongs to one of the three types mentioned above.

Output
For each query of type Qb or Qr, print the required answer.

Constraints


1<=Q<=10^5


1<=x,y<=10^9



Sample Input
5
Qb 4 5
Qr 4 5
Qi
Qb 4 5
Qr 4 5

Sample Output
2
1
1
2

Explanation
With the initial configuration of the tree, Path from node 4 to node 5 is 4->2->5 and color of nodes on the path is B->R->B.  

Number of black nodes are 2.
Number of red nodes are 1. 

After Query Qi, New configuration of the path from node 4 to node 5 is R->B->R.

Number of black nodes are 1.
Number of red nodes are 2. 


Scoring

 Subtask #1: 1<=Q<=100  1<=x,y<=1000   	         	                        : 27 pts
 Subtask #2: 1<=Q<=10^3  1<=x,y<=10^5       :  25 pts

 Subtask #3: 1<=Q<=10^5  1<=x,y<=10^9       :  48 pts
root_node_color = 0
color_map = {0: "Black", 1: "Red"}

def parent(x):
	return x >> 1


def traverse(start, to):
	path, p = [], start
	while p != to:
		path += [p]
		p = parent(p)
	path += [p]
	return path


def get_lca(x_path, y_path):
	y_path_map = {}
	for i in xrange(len(y_path)):
		y_path_map[y_path[i]] = i

	for i in xrange(len(x_path)):
		p = x_path[i]
		if p in y_path_map:
			return i, y_path_map[p]
	return -1, -1


def get_color(x):
	global root_node_color
	path = traverse(x, 1)
	color = 1-root_node_color
	for p in path[::-1]:
		color = 1-color
	return color 


def _get_colored_nodes(x, y, color):
	# print "Searching for {} nodes...".format(color_map[color])
	x_path = traverse(x, 1)
	y_path = traverse(y, 1)
	# print "x_path={}\ny_path={}".format(x_path, y_path)

	lca, l = get_lca(x_path, y_path)
	lca_color = get_color(x_path[lca])
	# print "lca={}\nlca_color={}|{}".format(x_path[lca], lca_color, color_map[lca_color])

	colored_nodes = 0
	a = lca if lca_color == color else lca - 1
	b = l - 2 if lca_color == color else l - 1

	for j in xrange(a, -1, -2):
		colored_nodes += 1
	for j in xrange(b, -1, -2):
		colored_nodes += 1

	return colored_nodes


def solve_query(q, x=None, y=None):
	global root_node_color
	if q == 'Qi':
		root_node_color = 1 - root_node_color
	elif q == 'Qb':
		assert x is not None and y is not None
		return _get_colored_nodes(x, y, 0)
	elif q == 'Qr':
		assert x is not None and y is not None
		return _get_colored_nodes(x, y, 1)
	return None
	

# # solve_query("Qi", state)
# print solve_query("Qb", 5000, 5000)
# print solve_query("Qr", 4000, 5000)

# solve_query("Qi")
# print solve_query("Qb", 5000, 5000)
# print solve_query("Qr", 5000, 5000)



def main():
	T = int(raw_input())
	for t in xrange(T):
		q = raw_input()
		if q.startswith("Qi"):
			solve_query("Qi")
		else:
			q = q.strip().split()
			print solve_query(q[0], int(q[1]), int(q[2]))
			# if r is not None:
				# output += [str(r)]
				# print r
	# print "\n".join(output)

if __name__ == '__main__':
	main()