output_description: Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th
  query.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      Q
      l_1 r_1
      :
      l_Q r_Q
attempt: #include <iostream>
  #include <fstream>
  #include <cstdio>
  #include <cmath>
  #include <vector>
  #include <cstring>
  #include <string>
  #include <set>
  #include <map>
  #include <stack>
  #include <queue>
  #include <algorithm>
  #include <climits>
  using namespace std;
  
  #define REP(i,n) for(int i=0; i<n; ++i)
  #define FOR(i,a,b) for(int i=a; i<=b; ++i)
  #define FORR(i,a,b) for (int i=a; i>=b; --i)
  #define ALL(c) (c).begin(), (c).end()
  
  typedef long long ll;
  typedef vector<int> VI;
  typedef vector<ll> VL;
  
  
  const int N_MAX = 100001;
  VI prime;
  void generate_prime() {
      prime.push_back(2); 
      FOR(i, 3, N_MAX) {
          for(auto p : prime) {
              if(i % p == 0) break;
              if(p > sqrt(i)) {
                  prime.push_back(i);
                  break;
              }
          }
      }
  }
  
  int main(){
      cin.tie(0);
      ios::sync_with_stdio(false);
      generate_prime();
      set<int> prime1(ALL(prime));
      set<int> prime2;
      for(auto& p : prime1) {
          if(p == 2) continue;
          if(prime1.count((p + 1) / 2) == 1) prime2.insert(p);
      }
      VI ans(N_MAX);
      ans[0] = 0;
      FOR(i, 1, N_MAX - 1) {
          if(prime2.count(i) == 1) ans[i] = ans[i - 1] + 1;
          else ans[i] = ans[i - 1];
      }
      
      int q;
      cin >> q;
      REP(i, q) {
          int l, r;
          cin >> l >> r;
          cout << ans[r] - ans[l - 1] << '\n';
      }
      return 0;
  }
  
problem_description: Statement
  
  We say that a odd number N is _similar to 2017_ when both N and (N+1)/2 are
  prime.
  
  You are given Q queries.
  
  In the i-th query, given two odd numbers l_i and r_i, find the number of odd
  numbers x similar to 2017 such that l_i ≤ x ≤ r_i.
samples: [{"input": "1\n    3 7", "output": "2\n    \n\n  * 3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.\n  * 5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.\n  * 7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.\n\nThus, the response to the first query should be 2.\n\n* * *"}, {"input": "4\n    13 13\n    7 11\n    7 11\n    2017 2017", "output": "1\n    0\n    0\n    1\n    \n\nNote that 2017 is also similar to 2017.\n\n* * *"}, {"input": "6\n    1 53\n    13 91\n    37 55\n    19 51\n    73 91\n    13 49", "output": "4\n    4\n    1\n    1\n    1\n    2"}]