# include <bits/stdc++.h>

using namespace std ;

const int N = 1e6 ;
//vector < int > pr[N + 1] ;
int num[N + 1] , cnt[N + 1] ;
int dis[N + 1] ;
bool vis[N + 1] , st[N + 1] , tmp[N + 1] ;
void solve()
{
	int l , r ;
	scanf("%d%d" , &l , &r) ;
	int pos = 0 ;
	for ( int i = l ; i <= r ; i++ )
		if ( cnt[i] == 1 )
		{
			pos = i ;
			break ;
		}
	if ( ! pos )
	{
		vis[l] = true ;
		for ( int i = l + 1 ; i <= r ; i++ ) dis[i] = cnt[l] + cnt[i] - cnt[__gcd( l , i )] , vis[i] = false ;
		int ans = 0 ;
		for ( int i = l + 1 ; i <= r ; i++ )
		{
			int pos = 0 ;
			for ( int j = l ; j <= r ; j++ )
			{
				if ( ! vis[j] ) 
				{
					if ( ! pos || dis[pos] > dis[j] ) pos = j ;
				}
			}
			ans += dis[pos] ;
			vis[pos] = true ;
			for ( int j = l ; j <= r ; j++ ) dis[j] = min( dis[j] , cnt[pos] + cnt[j] - cnt[__gcd( pos , j )] ) ; 
		}
		printf("%d\n" , ans) ;
	}
	else
	{
		int ans = -2 ;
		for ( int j = l ; j <= r ; j++ ) ans += cnt[j] ;
//		printf("ans:%d\n" , ans) ;
		for ( int j = 1 ; j <= r ; j++ ) st[j] = tmp[j] = false ;
		for ( int j = l ; j <= r ; j++ ) st[num[j]] = true ;
		for ( int j = 1 ; j <= r ; j++ )
		{
			if ( ! st[j] ) continue ;
			if ( ! tmp[j] ) ans++ ;
			for ( int k = j + j ; k <= r ; k += j ) tmp[k] = true ;
		}
		printf("%d\n" , ans) ;
	}
}
int main()
{
	for ( int i = 1 ; i <= N ; i++ )
	{
		num[i] = 1 ;
		int t = i ; 
		for ( int j = 2 ; j * j <= t ; j++ )
		{
			if ( t % j == 0 )
			{
				num[i] *= j ;
//				pr[i].push_back( j ) ;
				cnt[i] ++ ;
				while ( t % j == 0 ) t /= j ;
			}
		}
		if ( t != 1 ) num[i] *= t , cnt[i] ++ ;
//		printf("cnt[%d] %d\n" , i , cnt[i]) ;
	}
//	int ans = 0 ;
//	for ( int i = 1 ; i <= N ; i++ ) ans += pr[i].size() ;
//	printf("%d\n" , ans) ;
	int t ;
	scanf("%d" , &t) ;
	while ( t -- ) solve() ;
	return 0 ;
}