Binary GCD

#Python code to find GCD of two numbers using Binary GCD algorithm

def gcd (a,b):
    if a==0:
        return b
    if b==0:
        return a
   
    shift=0
   
    while (a|b)&1 ==0:
        a>>=1
        b>>=1
        shift+=1
   
    while a&1==0:
        a>>=1
           
    while b:
        while b&1==0:
            b>>=1
        if a>b:
            t=a
            a=b
            b=t
       
        b=b-a
       
    return a<<shift               
   

for i in range(input()):
    a,b=raw_input().split()
    n=int(a)
    m=int(b)
   
    print gcd(n,m)