#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(0); cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;

const int N = 1e5 + 5;

int _, n, m;
int z[1001][1001];
int f[1001][1001];

int dfs(int a, int b) {
    if (a == 0 || b == 0) return 0;

    if (f[a][b] != -1) return f[a][b];
    if (z[a][b] == - 1)  z[b][a] = z[a][b] = __gcd(a, b);

    f[a][b] = max(dfs(a - 1, b), dfs(a, b - 1)) + (z[a][b] == 1);
    return f[b][a] = f[a][b];
}

int main() {
    IO;
    memset(z, -1, sizeof z);
    memset(f, -1, sizeof f);
    for (cin >> _; _; --_) {
        int a, b; cin >> a >> b;
        cout << dfs(a, b) << '\n';
    } 
    return 0;
}