There is Chef and Chef’s Crush who are playing a game of numbers.

Chef’s crush has a number $A$ and Chef has a number $B$.

Now, Chef wants Chef’s crush to win the game always, since she is his crush. The game ends when the greatest value of A^B is reached after performing some number of operations (possibly zero), Where ^ is Bitwise XOR.

Before performing any operation you have to ensure that both $A$ and $B$ have the same number of bits without any change in the values. It is not guaranteed that $A$ and $B$ should have same number of bits in the input.
For example, if $A$ is $2$ and $B$ is $15$, then the binary representation of both the numbers will have to be $0010$ and $1111$ respectively, before performing any operation.  
The operation is defined as  : 
- Right circular shift of the bits of only $B$ from MSB$_B$ to LSB$_B$ i.e. if we consider $B_1 B_2 B_3 B_4$ as binary number, then after one circular right shift, it would be $B_4 B_1 B_2 B_3$
They both are busy with themselves, can you find the number of operations to end the game?

-----Input :-----
- The first line of input contains $T$, (number of test cases)  
- Then each of the next $T$ lines contain : two integers $A$ and $B$ respectively.

-----Output :-----
For each test case print two space-separated integers, The number of operations to end the game and value of A^B when the game ends.

-----Constraints :-----
- $1 \leq T \leq100$ 
- $1\leq A,B \leq 10^{18}$

-----Subtasks  :-----
- 30 Points: $1\leq A,B \leq 10^5$
- 70 Points: Original Constraints

-----Sample Input :-----
1
4 5

-----Sample Output :-----
2 7

-----Explanation  :-----
Binary  representation of  $4$ is $100$ and binary  representation  $5$ is $101$.   
- After operation $1$ : $B$ $=$ $110$, so A^B $=$ $2$ 
- After operation $2$ : $B$ $=$ $011$, so A^B $=$ $7$ 
So, the value of A^B will be $7$. Which is the greatest possible value for A^B and the number of operations are $2$.

Difficulty: interview

Starter code:

Solutions:

def main():
 t = int(input())
 while (t):
  m, n = map(int, input().split())
  a , b= bin(m)[2:],bin(n)[2:]
  #print(a,b)
  max = m^n
  if len(a)>len(b):
   diff =len(a)-len(b)
   b= ("0"*diff)+b
   #print(b)
  elif len(a)<len(b):
   diff =len(b)-len(a)
   a= ("0"*diff)+a
   #print(a)
  ll = len(b)
  count= 0
  for i in range(ll-1):
   s= b[ll-1] + b
   s= s[:ll]

   tt= m^ int(s,2)
   #print(m,s,tt)
   if tt>max:
    max =tt
    count= i+1
   b=s

  print(count,max)
  t-=1

def __starting_point():
 main()
__starting_point()

def bitLen(int_type):
 length = 0
 while (int_type):
  int_type >>= 1
  length += 1
 return(length)
def rot(b):
 b=b[-1]+b[:-1]
 return b
for __ in range(int(input())):
 ans=0
 r=0
 x=0
 c=0
 a, b = map(int, input().split())
 if a>=b:
  r = bitLen(a)
  b=(bitLen(a)-bitLen(b))*'0'+bin(b).replace('0b','')
  a=bin(a).replace('0b','')
 else:
  r = bitLen(b)
  a = (bitLen(b) - bitLen(a)) * '0' + bin(a).replace('0b', '')
  b = bin(b).replace('0b', '')
 for d in range(r):
  x=int(a,2)^int(b,2)
  b=rot(b)
  if ans < x:
   ans=x
   c=d
 print(c,ans)

try:
 def ts(s):  
  str1 = "" 
  for ele in s:  
   str1 += ele 
  return str1 
 
 for _ in range(int(input())):
  x,y=[int(x) for x in input().split()]
  x=list(bin(x).replace("0b", ""))
  y=list(bin(y).replace("0b",""))
  xl=len(x)
  yl=len(y)
  if(xl<yl):
   for __ in range(yl-xl):
    x.insert(0,'0')
  else:
   for __ in range(xl-yl):
    y.insert(0,'0') 
  l=len(x)
  xor=-1
  rotations=-1
  for i in range(l):
   temp_xor=int(ts(x),2)^int(ts(y),2)
   if(temp_xor>xor):
    xor=temp_xor
    rotations=i
   temp=x.pop
   y.insert(0,y.pop())
  print(rotations,xor)
  
except:
 pass

t = int(input())
while(t):
 a, b = map(int ,input().split())
 stra = bin(a).replace("0b", "")
 strb = bin(b).replace("0b","")
 if(len(stra) == len(strb)):
  pass
 elif(len(stra) > len(strb)):
  addi = len(stra) - len(strb)
  for i in range(addi):
   strb = '0' + strb
 else:
  addi = len(strb) - len(stra)
  for i in range(addi):
   stra = '0'+ stra
 n = len(strb)
 maxi = int(stra, 2) ^ int(strb, 2)
 i = 0
 indi = 0
 tem = strb[-1] + strb[0:n-1]
 while(tem != strb):
  c = int(stra, 2) ^ int(tem, 2)
  i += 1
  if(c >= maxi):
   maxi = c
   indi = i
  tem = tem[-1] + tem[0:n-1]
 print(indi, maxi)
 t = t - 1

# cook your dish here
for i in range(int(input())):
 a,b=map(int, input().split())
 b=bin(b)[2:]
 b=list(map(str, b))
 for j in range (len(str(bin(a)[2:]))-len(b)):
  b.insert(0,"0")
 xor=a^int(("".join(b)),2)
 max=xor
 c=0
 for j in range(len(b)-1):
  b = (b[-1:] + b[:-1])
  xor=a^int(("".join(b)),2)
  if xor>max:
   max=xor
   c=j+1
 print(c, max)


def bint(var):
 decimale = 0
 l = len(var)
 for i in range(l):
  decimale += int(var[i])*(2**(l-i-1))
 return decimale
 
 
t = int(input())
for _ in range(t):
 a, b = map(int, input().split())
 a = bin(a)[2:]
 b = bin(b)[2:]
 if(len(a) > len(b)):
  b = "0"*(len(a)-len(b)) + b
 elif(len(b) > len(a)):
  a = "0"*(len(b)-len(a)) + a
 l = len(a)
 res =0
 val = bint(a)^bint(b)
 temp = b[-1] + b[:l-1]
 x = 1
 while(x < l):
  if(bint(a)^bint(temp) > val):
   val = bint(a)^bint(temp)
   res = x
  temp = temp[-1] + temp[:l-1]
  x += 1
 print(res, val)

from math import log2
def rotate(n, bits):
 if(n&1):
  n = n>>1 | 1<<bits
 else:
  n = n >> 1
 return n
t = int(input())
while(t > 0):
 t -= 1
 max_xor = 0
 count = 0
 max_count = 0
 a, b = map(int, input().split())
 a_bits = int(log2(a)+1)
 b_bits = int(log2(b)+1)
 if(a_bits > b_bits):
  bits = a_bits
 else:
  bits = b_bits
 c = bits
 bits -= 1
 while(c > 0):
  c -= 1
  c_xor = a^b
  if(c_xor > max_xor):
   max_xor = c_xor
   max_count = count
  b = rotate(b, bits)
  count += 1
 print(max_count, max_xor)

def dec(n):  
 return bin(n).replace("0b", "")
def ss(str):
 if len(str) <= 1:
  return str
 mid = str[1:len(str)]
 return mid + str[0]
def btd(q):      
 q1 = q 
 decimal, i, n = 0, 0, 0
 while(q != 0): 
  dec = q % 10
  decimal = decimal + dec * (2**i) 
  q= q//10
  i += 1
 return(decimal) 
t=int(input())
for iw in range(0,t):
 a=input()
 arr=[]
 
 we=[]
 x=a.split()
 string=str(dec(int(x[1])))
 string2=str(dec(int(x[0])))
 d=int(x[0])
 if(len(string)>len(string2)):
  l=len(string)
 else:
  l=len(string2)
  for lk in range(0,len(string2)-len(string)):
   string='0'+string
 for k in range(0,l):
  c=int(x[1])
  arr.append(d^c)
  string=ss(string)
  x[1]=btd(int(string))
 for h in range(0,len(arr)):
  if(max(arr)==arr[h]):
   if(h==0):
    we.append(0)
    break
   else:
    we.append(len(arr)-h)
 print(min(we),max(arr))

t=int(input())
while(t):
 l=input().split()
 a=int(l[0])
 b=int(l[1])
 a=str(bin(a).replace("0b",""))
 b=str(bin(b).replace("0b",""))
 if(len(a)!=len(b)):
  if(len(a)>len(b)):
   m=len(a)-len(b)
   b=("0"*m)+b
  else:
   m=len(b)-len(a)
   a=("0"*m)+a
 l=len(b)
 s1=b.count('1')
 s2=b.count('0')
 if(l==s1 or l==s2):
  j=int(a)^int(b)
  k=int(str(j),2)
  print(0,k)
 else:
  l1=[]
  o=int(a,2)
  p=int(b,2)
  q=o^p
  l1.append(q)
  for i in range(1,l):
   b=b[-1]+b[0:-1]
   c=int(b,2)
   l1.append(o^c)
  maxx=max(l1)
  print(l1.index(maxx),maxx)
 t-=1

try:
 def right_shift(x):
  temp = x+x
  return temp[len(x)-1:2*len(x)-1]
 
 for i in range(int(input())):    
  a , b = map(int,input().split(" "))
  a,b=bin(a)[2:] , bin(b)[2:]
 
  if(len(a)<len(b)):
   diff = len(b)-len(a)
   a="0"*diff+a
  elif(len(b)<len(a)):
   diff = len(a)-len(b)
   b="0"*diff+b 
 
  a=int(a,2) 
  maxi = a^int(b,2) 
  steps=0
 
  for i in range(1,len(b)):    
   b=right_shift(b) 
  
   if(a^int(b,2)>maxi):
    maxi=a^int(b,2)
    steps = i
 
  print(steps,maxi)
except:
 pass

# cook your dish here
def right_shift(x):
 temp = x+x
 return temp[len(x)-1:2*len(x)-1]
 
for i in range(int(input())):    
 a , b = map(int,input().split(" "))
 a,b=bin(a)[2:] , bin(b)[2:]
 
 if(len(a)<len(b)):
  diff = len(b)-len(a)
  a="0"*diff+a
 elif(len(b)<len(a)):
  diff = len(a)-len(b)
  b="0"*diff+b 
 
 a=int(a,2) 
 maxi = a^int(b,2) 
 steps=0
 
 for i in range(1,len(b)):    
  b=right_shift(b) 
  
  if(a^int(b,2)>maxi):
   maxi=a^int(b,2)
   steps = i
 
 print(steps,maxi)

# cook your dish here
try:
 def dectobin(a):
  r=[int(i) for i in bin(a)[2:]]
  return r
 def bintodec(a):
  r=int("".join(str(x) for x in a),2)
  return r
 def s(a):
  a=[a[-1]]+a[:-1]
  return a
 for i in range(int(input())):
  a,b=map(int,input().split())
  bina=dectobin(a)
  binb=dectobin(b)
  ans=[]
  ans.append(a^b)
  bits=len(bina)-len(binb)
  if bits<0:
   for j in range(bits):
    bina.insert(0,0)
  elif bits>0:
   for j in range(bits):
    binb.insert(0,0)
  for j in range(len(binb)):
   binb=s(binb)
   b=bintodec(binb)
   ans.append(a^b)
  print(ans.index(max(ans)),max(ans))
except:
 pass

def right_shift(x):
 temp = x+x
 return temp[len(x)-1:2*len(x)-1]
 
for i in range(int(input())):    
 a , b = map(int,input().split(" "))
 a,b=bin(a)[2:] , bin(b)[2:]
 
 if(len(a)<len(b)):
  diff = len(b)-len(a)
  a="0"*diff+a
 elif(len(b)<len(a)):
  diff = len(a)-len(b)
  b="0"*diff+b 
 
 a=int(a,2) 
 maxi = a^int(b,2) 
 steps=0
 
 for i in range(1,len(b)):    
  b=right_shift(b) 
  
  if(a^int(b,2)>maxi):
   maxi=a^int(b,2)
   steps = i
 
 print(steps,maxi)

for _ in range(int(input())):
 a,b=list(map(int,input().split()))
 ab=bin(a)[2:]
 bb=bin(b)[2:]
 n=abs(len(bb)-len(ab))
 if n>0:
  if len(bb)>len(ab):
   ab = "0"*n + ab
  else:
   bb = "0"*n + bb
 m=0
 count=0
 for i in range(len(bb)):
  l=int(ab,2)^int(bb,2)
  if l>m:
   m=l
   count=i
  bb =bb[-1] + bb
  bb=bb[:-1]
  
 print(count,m)


# cook your dish here
for i in range(int(input())):
 A,B=map(int, input().split())
 B=bin(B)[2:]
 B=list(map(str, B))
 for j in range (len(str(bin(A)[2:]))-len(B)):
  B.insert(0,"0")
 xor=A^int(("".join(B)),2)
 max=xor
 c=0
 for j in range(len(B)-1):
  B = (B[-1:] + B[:-1])
  xor=A^int(("".join(B)),2)
  if xor>max:
   max=xor
   c=j+1
 print(c, max)

t=int(input())
while(t):
 t-=1
 a,b=list(map(int,input().split()))
 a=bin(a).replace("0b","")
 b=bin(b).replace("0b","")
 s1=len(a)
 s2=len(b)
 if(s1!=s2):
  if(s1>s2):
   f=s1-s2
   b=(f*'0')+b
  else:
   f=s2-s1
   a=(f*'0')+a
 s1=len(a)
 s2=len(b)
 t1=b.count('1')
 t2=b.count('0')
 if(s2==t1 or s2==t2):
  n=int(a)^int(b)
  m=int(str(n),2)
  print(0,m)
 else:
  v=[]
  g=int(a,2)
  h=int(b,2)
  j=g^h
  v.append(j)
  for i in range(1,len(b)):
   b=b[-1]+b[0:-1]
   c=int(b,2)
   v.append(g^c)
  y=max(v)
  print(v.index(y),y)


import math
t = int(input())
for ti in range(t):
 a,b = map(int,input().split())
 mx = max(a,b)
 bit = int((math.log(mx) / math.log(2)) + 1)
 num = pow(2,bit) - 1
 res = a^b 
 cnt = 0
 rot = 0
 for i in range(1,bit):
  if b%2==0:
   b//=2
  else:
   b+=num 
   b//=2
  ans = a^b
  cnt+=1
  if ans>res:
   res=ans
   rot=cnt
 print(str(rot)+" "+str(res))