unittest
{
	assert( [ "1", "3 7" ].parse.expand.solve == "2" );
	assert( [ "4", "13 13", "7 11", "7 11", "2017 2017" ].parse.expand.solve == "1\n0\n0\n1" );
	assert( [ "6", "1 53", "13 91", "37 55", "19 51", "73 91", "13 49" ].parse.expand.solve == "4\n4\n1\n1\n1\n2" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto q = input.front.to!( long );
	auto lrs = new long[ 2 ][ q ];
	foreach( ref lr; lrs )
	{
		input.popFront;
		lr = input.front.split.to!( long[] );
	}
	return tuple( lrs );
}

auto solve( long[ 2 ][] lrs )
{
	// 累積和表を作成
	const M = 10L ^^ 5;
	auto cs = new long[ M + 1 ];
	auto ps = M.primes;
	bool[ long ] pps;
	for( auto n = 2L; n < cs.length; n++ )
	{
		cs[ n ] = cs[ n - 1 ];
		if( ps.empty || n < ps.front ) continue;
		if( ( n + 1 ) / 2 in pps ) cs[ n ]++;
		pps[ ps.front ] = true;
		ps.popFront;
	}
	
	// クエリを処理
	auto anss = new long[ lrs.length ];
	foreach( ref ans, lr; lockstep( anss, lrs ) )
	{
		ans = cs[ lr[ 1 ] ] - cs[ lr[ 0 ] - 1 ];
	}
	return anss.to!( string[] ).join( "\n" );
}

// 素数列
auto primes( long x )
{
	Appender!( long[] ) ps;
	if( x < 2 ) return ps.data;
	
	auto cs = new bool[]( x + 1 );
	ps ~= 2L;
	for( auto i = 3L; i * i < cs.length; i += 2 )
	{
		if( cs[ i ] ) continue;
		for( auto j = i; i * j < cs.length; j++ )
		{
			cs[ i * j ] = true;
		}
	}
	for( auto i = 3L; i < cs.length; i += 2 )
	{
		if( !cs[ i ] ) ps ~= i;
	}
	return ps.data;
}
