#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 1e6 + 7 ;
int cnt[ MAXN ] ;

void init ( ) {
    for ( int i = 2 ; i < MAXN ; ++ i ) {
        if ( cnt[ i ] != 0 ) { continue ; }
        for ( int j = i ; j < MAXN ; j += i ) {
            ++ cnt[ j ] ; 
        }
    }
}

int prv[ MAXN ] , rnk[ MAXN ] ;
vector < pii > v[ MAXN ] ;
int sz[ MAXN ] , tp[ MAXN ] ;
priority_queue < pii > q ;

int get ( int x ) {
    if ( prv[ x ] == -1 ) { return x ; }
    int y = get ( prv[ x ] ) ;
    prv[ x ] = y ;
    return y ;
}

void unite ( int x , int y ) {
    int k1 = get ( x ) , k2 = get ( y ) ;
    if ( k1 == k2 ) { return ; }
    if ( rnk[ k1 ] < rnk[ k2 ] ) { swap ( k1 , k2 ) ; }
    rnk[ k1 ] += ( rnk[ k1 ] == rnk[ k2 ] ) ;
    prv[ k2 ] = k1 ;
}

void ext ( int x ) {
    while ( tp[ x ] < sz[ x ] ) {
        if ( get ( v[ x ][ 0 ].se ) != get ( v[ x ][ tp[ x ] ].se ) ) {
            q.push ( { -(v[ x ][ 0 ].fi + v[ x ][ tp[ x ] ].fi - cnt[ x ]) , x } ) ;
            ++ tp[ x ] ;
            return ;
        }
        ++ tp[ x ] ;
    }
}

void solve ( ) {
    int l , r ; cin >> l >> r ;
    for ( int i = 0 ; i <= r ; ++ i ) {
        prv[ i ] = -1 , rnk[ i ] = 0 ;
        v[ i ].clear ( ) ;
    }
    while ( q.empty ( ) == false ) { q.pop ( ) ; }
    // int tot = 0 ;
    for ( int x = 1 ; x <= r ; ++ x ) {
        for ( int val = x ; val <= r ; val += x ) {
            if ( val >= l ) {
                if ( __gcd ( val , x ) != x ) { continue ; }
                v[ x ].push_back ( { cnt[ val ] , val } ) ;
                // ++ tot ;
            }
        }
        // sort ( v[ x ].begin ( ) , v[ x ].end ( ) ) ;
        sz[ x ] = v[ x ].size ( ) ;
        tp[ x ] = 1 ;
        int hh = 0 ;
        if ( x == 1 ) { hh = 1 ; }
        for ( int targ = 1 ; targ <= 7 ; ++ targ ) {
            for ( int i = hh ; i < sz[ x ] ; ++ i ) {
                if ( v[ x ][ i ].fi == targ ) {
                    swap ( v[ x ][ i ] , v[ x ][ hh ] ) ;
                    ++ hh ;
                }
            }
        }
        ext ( x ) ;
    }
    // printf ( "tot = %d\n" , tot ) ;
    // return ;
    int ctr = 0 ;
    int ans = 0 ;
    while ( ctr < ( r - l + 1 ) - 1 && q.empty ( ) == false ) {
        auto [ sub , wh ] = q.top ( ) ;
        q.pop ( ) ;
        int x = v[ wh ][ 0 ].se ;
        int y = v[ wh ][ tp[ wh ] - 1 ].se ;
        if ( get ( x ) != get ( y ) ) { 
            unite ( x , y ) ;
            ans -= sub ;
            ++ ctr ;
        }
        if ( tp[ wh ] < sz[ wh ] ) { ext ( wh ) ; }
    }
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    init ( ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}