#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 2000 + 100;
const int mod = 1e9 + 7;
#define f(x) (x+x)
int d[1001][1001];
int gcd(int x, int y){
    return !y? x : gcd(y, x%y);
}
int main(){
    int t;
    scanf("%d", &t);
    //d[1][1] = 1;
    for(int i = 1; i <= 1000; ++i){
        for(int j = 1; j <= 1000; ++j){
            d[i][j] = max(d[i-1][j], d[i][j-1]);
            if(gcd(i, j) == 1) d[i][j]+=1;
        }
    }
    while(t--){
        int x, y;
        scanf("%d%d", &x, &y);
       
        printf("%d\n", d[x][y]);
    }
    return 0;
}