using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.ExceptionServices;
using System.Text;

namespace AtCoder.ABC
{
    class QuestionD
	{
		public static void Main(string[] args)
		{
			var scanner = new Scanner();

			var a = Primes(100000).ToArray();

			var prime = new bool[100001];

			foreach(var aa in a) {
				prime[aa] = true;
			}

			var is2017 = new bool[100001];

			for(int i = 1; i < 100001; i += 2) {
				var ii = (i + 1) / 2;

				if(prime[i] && prime[ii]) {
					is2017[i] = true;
				}
			}

			var sum2017 = new int[100001];
			var sum = 0;
			for(int i = 0; i < 100001; i++) {
				if (is2017[i]) {
					sum++;
				}

				sum2017[i] = sum;
			}

			var q = scanner.Int();
			var ans = new int[q];

			for (int i = 0; i < q; i++) {
				var (l, r) = scanner.Int2();

				ans[i] = sum2017[r] - sum2017[l - 1];
			}

			foreach (var aa in ans) {
				Console.WriteLine(aa);
			}
		}

		static IEnumerable<int> Primes(int maxnum)
		{
			yield return 2;
			yield return 3;
			var sieve = new BitArray(maxnum + 1);
			int squareroot = (int)Math.Sqrt(maxnum);
			for (int i = 2; i <= squareroot; i++) {
				if (sieve[i] == false) {
					for (int n = i * 2; n <= maxnum; n += i)
						sieve[n] = true;
				}
				for (int n = i * i + 1; n <= maxnum && n < (i + 1) * (i + 1); n++) {
					if (!sieve[n])
						yield return n;
				}
			}
		}

		public class Scanner
		{
			private readonly char[] delimiter_ = new char[] { ' ' };
			private readonly string filePath_;
			private readonly Func<string> reader_;
			private string[] buf_;
			private int index_;

			public Scanner(string file = "")
			{
				if (string.IsNullOrWhiteSpace(file)) {
					reader_ = Console.ReadLine;
				} else {
					filePath_ = file;
					var fs = new StreamReader(file);
					reader_ = fs.ReadLine;
				}
				buf_ = new string[0];
				index_ = 0;
			}

			public string NextLine() => reader_();
			public string Next()
			{
				if (index_ < buf_.Length) {
					return buf_[index_++];
				}

				string st = reader_();
				while (st == "") {
					st = reader_();
				}

				buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
				if (buf_.Length == 0) {
					return Next();
				}

				index_ = 0;
				return buf_[index_++];
			}

			public int Int() => int.Parse(Next());
			public long Long() => long.Parse(Next());
			public double Double() => double.Parse(Next());

			public int[] ArrayInt(int N, int add = 0)
			{
				int[] Array = new int[N];
				for (int i = 0; i < N; i++) {
					Array[i] = Int() + add;
				}
				return Array;
			}

			public long[] ArrayLong(int N, long add = 0)
			{
				long[] Array = new long[N];
				for (int i = 0; i < N; i++) {
					Array[i] = Long() + add;
				}
				return Array;
			}

			public double[] ArrayDouble(int N, double add = 0)
			{
				double[] Array = new double[N];
				for (int i = 0; i < N; i++) {
					Array[i] = Double() + add;
				}
				return Array;
			}

			public (int, int) Int2(int add = 0)
			{
				var array = ArrayInt(2, add);
				return (array[0], array[1]);
			}

			public (int, int, int) Int3(int add = 0)
			{
				var array = ArrayInt(3, add);
				return (array[0], array[1], array[2]);
			}

			public (long, long) Long2(int add = 0)
			{
				var array = ArrayLong(2, add);
				return (array[0], array[1]);
			}

			public (long, long, long) Long3(int add = 0)
			{
				var array = ArrayLong(3, add);
				return (array[0], array[1], array[2]);
			}

			public (double, double) Double2(int add = 0)
			{
				var array = ArrayDouble(2, add);
				return (array[0], array[1]);
			}

			public (double, double, double) Double3(int add = 0)
			{
				var array = ArrayDouble(3, add);
				return (array[0], array[1], array[2]);
			}

			public void Save(string text)
			{
				if (string.IsNullOrWhiteSpace(filePath_)) {
					return;
				}

				File.WriteAllText(filePath_ + "_output.txt", text);
			}
		}
	}
}


Measured memory_bytes: 47924