n = input()
while n:
    try:
        l = raw_input().split()
        a = int(l[0])
        b = int(l[1])
        sum1=0
        
        mul=1
        cn=0
        for i in bin:
            mul = a**cn
            cn+=1
            if i == '1':
                sum1 = sum1 + (mul)
        print str(sum1)
        n-=1
    except:
        break