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
biA9IGlucHV0KCkKd2hpbGUgbjoKICAgIHRyeToKICAgICAgICBsID0gcmF3X2lucHV0KCkuc3BsaXQoKQogICAgICAgIGEgPSBpbnQobFswXSkKICAgICAgICBiID0gaW50KGxbMV0pCiAgICAgICAgc3VtMT0wCiAgICAgICAgCiAgICAgICAgbXVsPTEKICAgICAgICBjbj0wCiAgICAgICAgZm9yIGkgaW4gYmluOgogICAgICAgICAgICBtdWwgPSBhKipjbgogICAgICAgICAgICBjbis9MQogICAgICAgICAgICBpZiBpID09ICcxJzoKICAgICAgICAgICAgICAgIHN1bTEgPSBzdW0xICsgKG11bCkKICAgICAgICBwcmludCBzdHIoc3VtMSkKICAgICAgICBuLT0xCiAgICBleGNlcHQ6CiAgICAgICAgYnJlYWsK