import sys
t=int(input()) #liczba partii
if(t<1 or t>10):
sys.exit()
j=0
r=0
lista=[]
while(j<t):
a=int(input())
if(a<1 or a>1000000000):
sys.exit()
b=int(input())
if(b<1 or b>1000000000):
sys.exit()
while(a>=0 and b>=0):
if(a==0 or b==0):
lista.append(a+b)
break
if(a<b):
b=b-a
elif(b<a):
a=a-b
elif(a==b):
lista.append(a+b)
break
j=j+1
for i in lista:
print(i);
aW1wb3J0IHN5cwoKdD1pbnQoaW5wdXQoKSkgI2xpY3piYSBwYXJ0aWkKaWYodDwxIG9yIHQ+MTApOgogICAgc3lzLmV4aXQoKQogCmo9MApyPTAKbGlzdGE9W10Kd2hpbGUoajx0KToKICAgIGE9aW50KGlucHV0KCkpCiAgICBpZihhPDEgb3IgYT4xMDAwMDAwMDAwKToKICAgICAgICBzeXMuZXhpdCgpCiAgICBiPWludChpbnB1dCgpKQogICAgaWYoYjwxIG9yIGI+MTAwMDAwMDAwMCk6CiAgICAgICAgc3lzLmV4aXQoKQogICAgd2hpbGUoYT49MCBhbmQgYj49MCk6ICAKICAgICAgICBpZihhPT0wIG9yIGI9PTApOgogICAgICAgICAgICBsaXN0YS5hcHBlbmQoYStiKQogICAgICAgICAgICBicmVhawogICAgICAgIGlmKGE8Yik6CiAgICAgICAgICAgIGI9Yi1hCiAgICAgICAgZWxpZihiPGEpOgogICAgICAgICAgICBhPWEtYiAgICAgICAgICAKICAgICAgICBlbGlmKGE9PWIpOiAgICAKICAgICAgICAgICAgbGlzdGEuYXBwZW5kKGErYikKICAgICAgICAgICAgYnJlYWsKICAgIGo9aisxCgpmb3IgaSBpbiBsaXN0YToKICAgIHByaW50KGkpOwoK