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 <cstring>
  #include <iostream>
  #include <vector>
  
  using namespace std;
  
  class Prime {
  // n以下の素数を列挙する
  public:
    const int n;
    vector<bool> is_prime;
    vector<int> primes;
    Prime(int size) : n(size), is_prime(n, true) {
      is_prime[0] = false;
      is_prime[1] = false;
      for (int i = 2; i <= n; ++i) {
        if (!is_prime[i]) continue;
        primes.push_back(i);
        int tmp = 2*i;
        while (tmp <= n) {
          is_prime[tmp] = false;
          tmp += i;
        }
      }
    }
  
    bool check(int x) { return is_prime[x]; }
  };
  
  int dp[100001];
  
  int main() {
    memset(dp, 0, sizeof(dp));
    Prime prime(100001);
    for (int i = 1; i <= 100000; ++i) {
      dp[i] = dp[i-1];
      if (i % 2 == 0) continue;
      if (!prime.check(i)) continue;
      if (!prime.check((i+1)/2)) continue;
      dp[i] += 1;
    }
  
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
      int l, r;
      cin >> l >> r;
      cout << dp[r] - dp[l-1] << endl;
    }
  }
  
  
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"}]