#include<bits/stdc++.h>

using namespace std;

const int N = 1000'100;
const int INF = (int) 1e9;

bool cmp[N];
int rn[N];
vector< int > primes[N];

int solve()
{
  int l, r;
  cin >> l >> r;

  const int n = ( r - l + 1 );

  vector< int > v;
  for( int i = l; i <= r; ++ i )
    v.push_back( rn[i] );

  sort( v.begin(), v.end() );

  vector< int > mn_cost_mul( r + 1, INF );

  int ans = 0;
  for( int i = 0; i < n; ++ i )
  {
    const int x = v[i];
    const int wx = (int) primes[x].size();

    int mn_cost = INF;
    for( int mask = 0; mask < ( 1 << wx ); ++ mask )
    {
      int div = 1, wdiv = 0;
      for( int j = 0; j < wx; ++ j )
        if( mask >> j & 1 )
          div *= primes[x][j], ++wdiv;

      mn_cost = min( mn_cost, mn_cost_mul[div] - wdiv );
      mn_cost_mul[div] = min( mn_cost_mul[div], wx );
    }

    mn_cost += wx;
    if( i != 0 ) ans += mn_cost;
  }

  return ans;
}

int main()
{
  cin.tie( NULL );
  ios_base::sync_with_stdio( 0 );

  iota( rn, rn + N, 0 );
  for( int i = 2; i < N; ++ i )
  {
    if( !cmp[i] )
    {
      long long i2 = 1LL * i * i;

      for( int j = i; j < N; j += i )
      {
        cmp[j] = true;
        if( j % i2 == 0 )
          rn[j] = j/i;

        primes[j].push_back( i );
      }
    } 

    if( rn[i] != i )
      rn[i] = rn[rn[i]];
  }


  int t;
  cin >> t;
  while( t-- )
    cout << solve() << '\n';

  return 0;
}