#include<stdio.h>
static int s[1001][1001];

int gcd(int x, int y)
{
    return y ? gcd(y, x % y) : x;
}
int main()
{
    for (int i = 1; i <= 1000; i++){
        s[1][i] = i;
        s[i][1] = i;
    }
    for(int i = 2; i <= 1000; i++){
        for (int j = i; j <= 1000; j++) {
            if (s[i - 1][j] < s[i][j - 1]) {
                s[i][j] = s[i][j - 1];
            }
            else {
                s[i][j] = s[i - 1][j];
            }
            if (gcd(i, j) == 1) {
                s[i][j] += 1;
            }
            s[j][i] = s[i][j];
        }
    }
    int t;
    scanf("%d", &t);
    for (int r = 0; r < t; r++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        printf("%d\n", s[a][b]);
    }
    return 0;
}