#include <bits/stdc++.h>
using namespace std;
int primes[] = {
    3,     5,     13,    37,    61,    73,    157,   193,   277,   313,   397,
    421,   457,   541,   613,   661,   673,   733,   757,   877,   997,   1093,
    1153,  1201,  1213,  1237,  1321,  1381,  1453,  1621,  1657,  1753,  1873,
    1933,  1993,  2017,  2137,  2341,  2473,  2557,  2593,  2797,  2857,  2917,
    3061,  3217,  3253,  3313,  3517,  3733,  4021,  4057,  4177,  4261,  4273,
    4357,  4441,  4561,  4621,  4933,  5077,  5101,  5113,  5233,  5413,  5437,
    5581,  5701,  6037,  6073,  6121,  6133,  6217,  6337,  6361,  6373,  6637,
    6661,  6781,  6997,  7057,  7213,  7393,  7417,  7477,  7537,  7753,  7933,
    8053,  8101,  8221,  8317,  8353,  8461,  8521,  8677,  8713,  8893,  9013,
    9133,  9181,  9241,  9277,  9601,  9661,  9721,  9817,  9901,  9973,  10333,
    10357, 10453, 10837, 10861, 10957, 11113, 11161, 11317, 11497, 11677, 11701,
    12073, 12157, 12241, 12301, 12421, 12433, 12457, 12541, 12553, 12601, 12721,
    12757, 12841, 12853, 13093, 13381, 13417, 13681, 13921, 13933, 14437, 14593,
    14737, 14821, 15013, 15073, 15121, 15241, 15277, 15361, 15373, 15733, 15901,
    16033, 16333, 16381, 16417, 16573, 16633, 16657, 16921, 17041, 17053, 17077,
    17257, 17293, 17377, 17881, 18013, 18097, 18133, 18181, 18217, 18253, 18301,
    18313, 18397, 18481, 18553, 18637, 18793, 19237, 19441, 19477, 19717, 19801,
    19813, 19861, 20353, 20533, 20641, 20857, 21001, 21061, 21193, 21277, 21313,
    21577, 21661, 21673, 21817, 22093, 22501, 22573, 22621, 22993, 23053, 23173,
    23557, 23677, 23773, 23917, 24097, 24421, 24481, 24781, 24841, 25033, 25153,
    25237, 25561, 25657, 25933, 26017, 26293, 26317, 26437, 26497, 26821, 26833,
    26881, 26953, 27073, 27253, 27337, 27361, 27457, 27997, 28057, 28297, 28393,
    28813, 28837, 28921, 29101, 29473, 29641, 30181, 30241, 30517, 30553, 30577,
    30637, 30661, 30697, 30781, 30853, 31081, 31237, 31321, 31333, 31357, 31477,
    31573, 31873, 31981, 32173, 32377, 32497, 32533, 32833, 33037, 33301, 33457,
    33493, 33757, 33961, 34057, 34213, 34273, 34381, 34513, 34897, 34981, 35317,
    35521, 35677, 35977, 36097, 36241, 36433, 36457, 36793, 36877, 36901, 36913,
    37273, 37321, 37357, 37573, 37717, 37957, 38281, 38461, 38833, 38953, 38977,
    39217, 39373, 39397, 39733, 40093, 40177, 40213, 40693, 40813, 41017, 41221,
    41281, 41413, 41617, 41893, 42061, 42337, 42373, 42793, 42961, 43117, 43177,
    43201, 43321, 43573, 43597, 43633, 43717, 44053, 44101, 44221, 44257, 44293,
    44893, 45061, 45337, 45433, 45481, 45553, 45613, 45841, 46021, 46141, 46261,
    46861, 46993, 47017, 47161, 47353, 47521, 47533, 47653, 47713, 47737, 47797,
    47857, 48121, 48193, 48337, 48673, 48757, 48781, 49033, 49261, 49393, 49417,
    49597, 49681, 49957, 50221, 50341, 50377, 50821, 50893, 51157, 51217, 51241,
    51481, 51517, 51637, 52057, 52081, 52237, 52321, 52453, 52501, 52813, 52861,
    52957, 53077, 53113, 53281, 53401, 53917, 54121, 54133, 54181, 54217, 54421,
    54517, 54541, 54673, 54721, 54973, 55057, 55381, 55501, 55633, 55837, 55921,
    55933, 56053, 56101, 56113, 56197, 56401, 56437, 56701, 56773, 56821, 56857,
    56893, 57073, 57097, 57193, 57241, 57373, 57457, 57853, 58153, 58417, 58441,
    58537, 58573, 58693, 59053, 59197, 59221, 59281, 59341, 59833, 60217, 60337,
    60373, 60637, 60733, 60937, 61057, 61153, 61261, 61297, 61561, 61657, 61681,
    61717, 61861, 62137, 62473, 62497, 62533, 62653, 62773, 63313, 63397, 63541,
    63697, 63781, 63913, 64153, 64237, 64381, 64513, 64717, 65173, 65293, 65413,
    65437, 65497, 65557, 65677, 65881, 66301, 66361, 66601, 66697, 66853, 66973,
    67057, 67153, 67273, 67477, 67537, 67741, 67777, 67933, 67993, 68113, 68281,
    68521, 68737, 69001, 69073, 69457, 69493, 69697, 69877, 70117, 70177, 70297,
    70501, 70621, 70921, 70981, 71233, 71341, 71353, 71593, 71821, 72073, 72481,
    72613, 72901, 72937, 73141, 73417, 73477, 73561, 73693, 74077, 74317, 74377,
    74713, 75013, 75133, 75181, 75721, 75793, 75913, 76333, 76561, 76597, 76753,
    77137, 77641, 78157, 78193, 78277, 78877, 78901, 79333, 79357, 79537, 79657,
    79693, 79801, 79873, 80077, 80173, 80221, 80473, 80701, 80713, 80917, 81013,
    81181, 81517, 81637, 81853, 82021, 82153, 82261, 82561, 82981, 83077, 83221,
    83233, 83437, 83617, 83701, 83773, 84121, 84313, 84673, 84697, 84793, 84913,
    85297, 85333, 85453, 85717, 85933, 86353, 86413, 87181, 87253, 87337, 87421,
    87433, 87517, 87553, 87973, 88117, 88177, 88237, 88261, 88513, 88741, 88897,
    88993, 89293, 89833, 89917, 90121, 91081, 91381, 91393, 91513, 91957, 92041,
    92557, 92761, 92821, 92893, 92941, 93097, 93133, 93493, 93637, 93913, 94033,
    94117, 94273, 94321, 94441, 94573, 94777, 94837, 94993, 95257, 95317, 95401,
    95581, 95617, 95713, 95737, 96097, 96157, 96181, 96493, 96517, 96973, 97081,
    97177, 97501, 97561, 97777, 97813, 98017, 98737, 98953, 99277, 99577, 99661,
    99877};
bool isPrime(int n) {
  int x = sqrt(n + 1);
  for (int i = 3; i <= x; i += 2)
    if (n % i == 0) return false;
  return true;
}
int BSL(int lo, int hi, int x) {
  int mid, tmp, i = -1;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    tmp = primes[mid];
    if (tmp >= x) {
      hi = mid - 1;
      i = mid;
    } else
      lo = mid + 1;
  }
  return i;
}
int BSR(int lo, int hi, int x) {
  int mid, tmp, i = -1;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    tmp = primes[mid];
    if (tmp <= x) {
      lo = mid + 1;
      i = mid;
    } else
      hi = mid - 1;
  }
  return i;
}
int main() {
  int cnt = 1;
  int x = sizeof primes / 4;
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    int a = BSL(0, x, l);
    int b = BSR(0, x, r);
    printf("%d\n", b - a + 1);
  }
  return 0;
}
