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
import math

q = int(raw_input())
switch = 0

def level(n):
  cnt = 0

  while n > 1:
    cnt += 1
    n >>= 1

  return cnt

def result(com, smaller, switch, n):
  n = float(n)

  if com == "Qb":
    if (switch == 0 and smaller % 2 == 0) or (switch == 1 and smaller % 2 == 1):
      return int(math.ceil(n/2))
    else:
      return int(math.floor(n/2))
  else:
    if (switch == 0 and smaller % 2 == 0) or (switch == 1 and smaller % 2 == 1):
      return int(math.floor(n/2))
    else:
      return int(math.ceil(n/2))

  raise("Hell")
  return None

def lca(x, y):
  l1 = level(x)
  l2 = level(y)
  n = abs(l1 - l2)
  
  if l1 < l2:
    ptr1 = y
    ptr2 = x
  else:
    ptr1 = x
    ptr2 = y

  while n != 0:
    ptr1 = ptr1 / 2
    n -= 1

  while ptr1 != ptr2:
    ptr1 = ptr1 / 2
    ptr2 = ptr2 / 2

  return ptr1

def color(com, level, switch):
  if com == "Qb":
    if level % 2 == switch :
      return 1
    else:
      return 0
  else:
    if level % 2 != switch :
      return 1
    else:
      return 0

for T in range(q):
  s = raw_input().split()

  if s[0] == "Qi":
    switch = (switch + 1)%2
  else:
    com, x, y = s[0], int(s[1]), int(s[2])
    lc = level(lca(x, y))
    l1 = level(x)
    l2 = level(y)
    #print lc, l1, l2, switch
    val = result(com, lc, switch, l1 - lc + 1) + result(com, lc, switch, l2 - lc + 1) - color(com, lc, switch)


    print val