#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<queue>
#include<stack>
#include<utility>
using namespace std;
#define ll long long
ll gcd(ll a,ll b) {
    return b?gcd(b,a%b):a;
}
int cnt[1001][1001];
int main() {
    for(int i=1;i<=1000;++i){
        for(int j=i;j<=1000;++j){
            cnt[i][j]=max(cnt[i-1][j],cnt[i][j-1]);
            if(gcd(i,j)==1) cnt[i][j]++;
        } 
    }
    int t,a,b;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&a,&b);
        if(a>b) swap(a,b);
        printf("%d\n",cnt[a][b]);
    } 
    return 0;
}