#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD, b >>= 1;
    }
    return res;
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int f[1005][1005] = {0};
int minp[1005] = {0}, prime[505], tot = 0;
int xa[1005], xb[1005], xc[1005];
int gcd_table[105][105];
const int N = 1000, SRT = 32;
void build(){
    // combine linear sieve with the preprocessing
    minp[1] = 1;
    xa[1] = xb[1] = xc[1] = 1;

    for (int i = 2; i <= N; ++i){
        if (!minp[i])
            prime[++tot] = i, minp[i] = i;
        for (int j = 1; j <= tot; ++j){
            if (1ll * i * prime[j] > N || prime[j] > minp[i]) break;
            minp[i * prime[j]] = prime[j];
        }
        
        int bf = i / minp[i];
        int xxa = xa[bf] * minp[i], xxb = xb[bf], xxc = xc[bf];
        if (xxa >= xxc) xa[i] = xxb, xb[i] = xxc, xc[i] = xxa;
        else {
            xc[i] = xxc;
            if (xxa >= xxb) xa[i] = xxb, xb[i] = xxa;
            else xa[i] = xxa, xb[i] = xxb;
        }
    }
    
    // build the map
    for (int i = 1; i <= SRT; ++i)
        gcd_table[i][0] = gcd_table[0][i] = i;
    for (int i = 1; i <= SRT; ++i)
        for (int j = 1; j <= i; ++j)
            gcd_table[i][j] = gcd_table[j][i] = gcd_table[i % j][j];
}
int query(int x, int y){
    int res = 1, tmp;
    if (1ll * xc[x] * xc[x] > x && y % xc[x] == 0)
        y /= xc[x], res *= xc[x];
    else if (1ll * xc[x] * xc[x] <= x){
        tmp = gcd_table[xc[x]][y % xc[x]];
        res *= tmp, y /= tmp;
    }
    tmp = gcd_table[xa[x]][y % xa[x]];
    res *= tmp, y /= tmp;
    tmp = gcd_table[xb[x]][y % xb[x]];
    res *= tmp, y /= tmp;
    return res;
}
void init(){
}
void solve(){
    int x = read(), y = read();
    printf("%d\n", f[x][y]);
}
int main(){
    int T = read();
    build();
    REP(i, 1, 1000)
        REP(j, 1, 1000)
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (query(i, j) == 1 ? 1: 0);
    while (T--){
        init();
        solve();
    }
    return 0;
}