#include <bits/stdc++.h>
using namespace std;
long long a,b,t;
ifstream fin("euclid2.in");
ofstream fout("euclid2.out");
int cmmdc(int u, int v)
{
    int shl = 0;
    while ( u && v && u!=v )
    {
        bool eu = !(u & 1);
        bool ev = !(v & 1);
        if ( eu && ev )
        {
            ++shl;
            u >>= 1;
            v >>= 1;
        }
        else if ( eu && !ev ) u >>= 1;
        else if ( !eu && ev ) v >>= 1;
        else if ( u>=v ) u = (u-v)>>1;
        else
        {
            int tmp = u;
            u = (v-u)>>1;
            v = tmp;
        }
    }
    return !u? v<<shl : u<<shl;
}
int main()
{
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        fout<<cmmdc(a,b)<<"\n";
    }
    return 0;
}