
 """
 Logic is pretty much self explained there, complexity should be also fairly low,
 but heck was it tricky
 """
 def answer(n):

 # n is given as a string so let's cast it
 n=int(n)
 res = 0

 while(n!=1):
 # if our number is odd then let's just divide by 2
 if(n%2==0):
 n=n/2
 # now this is the tricky part and took me a bunch of googling to figure
 # out: instead of going the brute force O(n²) way and just trying out
 # every possibility in nested loops you can actually figure out if you
 # should add or remove: when rightmost bits are set as "111" the
 # preferred operation is to add, as that would push back everything as
 # 000s, while any other case would be faster the other way around.
 elif((n==3) or ((n+1)&n) > ((n1)&(n2))):
 n=1
 else:
 n+=1
 res+=1
 return res
