#include <iostream>
#include <cmath>
 
using namespace std;
 
int main(int argc, char* argv[])
{
    int data, **arrayPointer, *results, counter = 0;
    cin >> data;
    results = new int[data];
    arrayPointer = new int*[data];
    for (int i = 0; i < data; ++i)
    {
        // Zrób tablicę 2D, a następnie wczytaj do niej a, b;
        arrayPointer[i] = new int[2];
        cin >> arrayPointer[i][0] >> arrayPointer[i][1];
 
    }
    for (int i = 0; i < data; ++i)
    {
        // Sprawdź czy A % B = 0?
        if(arrayPointer[i][0]%arrayPointer[i][1]==0)
        {
            // Sprawdź czy ewentualnie A = B?
            if(arrayPointer[i][0]==arrayPointer[i][1])
                // Jeśli tak przyjmij za counter połowę z max(A,B);
                counter = max(arrayPointer[i][0], arrayPointer[i][1])/2;
            else
                // W przeciwnym wypadku counter = min(a,B);
                counter = min(arrayPointer[i][0], arrayPointer[i][1]);
        }
        else
            // A jeśli w ogóle nie to przyjmij za counter=A%B
            counter = arrayPointer[i][0]%arrayPointer[i][1];
 
            // Po "przycięciu" countera, sprawdź pozostałe możliwości.
        while(arrayPointer[i][0]%counter!=0 || arrayPointer[i][1]%counter!= 0)
            counter--;
 
        cout << counter << endl;
    }
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqIGFyZ3ZbXSkKewogICAgaW50IGRhdGEsICoqYXJyYXlQb2ludGVyLCAqcmVzdWx0cywgY291bnRlciA9IDA7CiAgICBjaW4gPj4gZGF0YTsKICAgIHJlc3VsdHMgPSBuZXcgaW50W2RhdGFdOwogICAgYXJyYXlQb2ludGVyID0gbmV3IGludCpbZGF0YV07CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGRhdGE7ICsraSkKICAgIHsKICAgICAgICAvLyBacsOzYiB0YWJsaWPEmSAyRCwgYSBuYXN0xJlwbmllIHdjenl0YWogZG8gbmllaiBhLCBiOwogICAgICAgIGFycmF5UG9pbnRlcltpXSA9IG5ldyBpbnRbMl07CiAgICAgICAgY2luID4+IGFycmF5UG9pbnRlcltpXVswXSA+PiBhcnJheVBvaW50ZXJbaV1bMV07CiAKICAgIH0KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZGF0YTsgKytpKQogICAgewogICAgICAgIC8vIFNwcmF3ZMW6IGN6eSBBICUgQiA9IDA/CiAgICAgICAgaWYoYXJyYXlQb2ludGVyW2ldWzBdJWFycmF5UG9pbnRlcltpXVsxXT09MCkKICAgICAgICB7CiAgICAgICAgICAgIC8vIFNwcmF3ZMW6IGN6eSBld2VudHVhbG5pZSBBID0gQj8KICAgICAgICAgICAgaWYoYXJyYXlQb2ludGVyW2ldWzBdPT1hcnJheVBvaW50ZXJbaV1bMV0pCiAgICAgICAgICAgICAgICAvLyBKZcWbbGkgdGFrIHByenlqbWlqIHphIGNvdW50ZXIgcG/Fgm93xJkgeiBtYXgoQSxCKTsKICAgICAgICAgICAgICAgIGNvdW50ZXIgPSBtYXgoYXJyYXlQb2ludGVyW2ldWzBdLCBhcnJheVBvaW50ZXJbaV1bMV0pLzI7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIC8vIFcgcHJ6ZWNpd255bSB3eXBhZGt1IGNvdW50ZXIgPSBtaW4oYSxCKTsKICAgICAgICAgICAgICAgIGNvdW50ZXIgPSBtaW4oYXJyYXlQb2ludGVyW2ldWzBdLCBhcnJheVBvaW50ZXJbaV1bMV0pOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgICAgIC8vIEEgamXFm2xpIHcgb2fDs2xlIG5pZSB0byBwcnp5am1paiB6YSBjb3VudGVyPUElQgogICAgICAgICAgICBjb3VudGVyID0gYXJyYXlQb2ludGVyW2ldWzBdJWFycmF5UG9pbnRlcltpXVsxXTsKIAogICAgICAgICAgICAvLyBQbyAicHJ6eWNpxJljaXUiIGNvdW50ZXJhLCBzcHJhd2TFuiBwb3pvc3RhxYJlIG1vxbxsaXdvxZtjaS4KICAgICAgICB3aGlsZShhcnJheVBvaW50ZXJbaV1bMF0lY291bnRlciE9MCB8fCBhcnJheVBvaW50ZXJbaV1bMV0lY291bnRlciE9IDApCiAgICAgICAgICAgIGNvdW50ZXItLTsKIAogICAgICAgIGNvdXQgPDwgY291bnRlciA8PCBlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0=

MTAwCjM2OTA0MCAxOTkzMTEKMTE4MTAzIDU3Nzg3MQo2NTk0NiAzMjQ4NzMKODgwMTQzIDYzMzEzNgo2NzcwNTcgMzYzMTIxCjU3NDk4IDgyNTg4NQo0NDY4MTMgOTIyNDQzCjg1OTI1OCA1OTgyNjEKOTUwNDc2IDkyNzE3Nwo4Nzk4ODcgMzQwMzc2CjMxNjYgMjI3NDE2CjUyMTkwNiAyMTMxODEKNzg3MzM4IDYyMDA4MQoyODY3OTEgNTU5NjE5CjQ4ODAwOCA5MjIwMTQKMjc2MDggNjQ2MTUxCjgxNDUyNiA3NDk1ODgKODIyMDQzIDc4MDkxOAoyMTQ3OTYgNjg3NjQ4CjE2MzIyNCA1Mjg5NjkKODgwOTI3IDU0OTA5NQoyNjE3MjMgODY5OTE3CjU0NDk4MCA4OTYzMzYKNTkwMjg3IDUwMjY5Ngo5MzU5ODMgMjI2ODEwCjMwNTI0MyA5ODIyMTEKNzM4MjUgMjgwNjIKNjYzMDA2IDQyOTExNgoxOTk2ODggMTg5NTYyCjYxMjU5NSA2NTM5MjcKNjUwMzEyIDI2MTc0Mwo4MTQzOSA1ODg3NTMKNjkxMDg2IDU4NzQ3Ngo2MjgwMTcgMTI1ODY3Cjg3ODIxNCAyMTcyNzQKODQ3OTUxIDI3MDg1MwoxMDc4MTMgNjQzNDk1CjgwODQwMyA4MTkxMDgKNzIyNTQ0IDI2NTkyNAoyMjk4MjAgNjUwNzI2CjE0NTc5NiA4MTE2MzMKNjE2ODI2IDgwODEzNQozMTI3OTMgMzAwMzkzCjM0NTYxNyA0OTg3MzEKMTMxMDUxIDI2NTA0OQo5OTExOTYgMzI5NTM3CjQ0MzcxNiAxNDcwNjEKMzAxMzgxIDk5MTEwNQo3MzkzOCA5OTEyMzcKNTI3NjI3IDE2Mjk2Mg==

100
369040 199311
118103 577871
65946 324873
880143 633136
677057 363121
57498 825885
446813 922443
859258 598261
950476 927177
879887 340376
3166 227416
521906 213181
787338 620081
286791 559619
488008 922014
27608 646151
814526 749588
822043 780918
214796 687648
163224 528969
880927 549095
261723 869917
544980 896336
590287 502696
935983 226810
305243 982211
73825 28062
663006 429116
199688 189562
612595 653927
650312 261743
81439 588753
691086 587476
628017 125867
878214 217274
847951 270853
107813 643495
808403 819108
722544 265924
229820 650726
145796 811633
616826 808135
312793 300393
345617 498731
131051 265049
991196 329537
443716 147061
301381 991105
73938 991237
527627 162962