oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

countfishes Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

countfishes.html

Problem Description

Rar the cat likes fishes and loves to include fishes in his favourite dish, fish soup. Since you all have provided great help and support in handling all the strings, he decided to reward you with the highest quality fish soup. However, in order to make the highest quality (tastiest) fish soup, he needs fish which can pass through a certain sieve which his ancestors has passed down for generations, known as the sieve of eratosthenes. By placing fishes on top of the sieve, the fish will be able to pass through the sieve if its weight is of a prime number (Eg. 2kg and 3kg) and sieve out those fishes that are not.

However, Rar the cat is not very smart, and doesn't know the weights of the fish he should be looking out for in the fish market. As such, to guarentee he has at least some fish to cook fish soup, he decides to buy fish of weight Pkg to Qkg inclusive, one each at intervals of 1kg. (Pkg, (P+1)kg, (P+2)kg ... (Q-2)kg, (Q-1)kg, Qkg)

Help Rar the cat calculate how many fishes he can use to cook his much coveted fish soup of the highest quality given P and Q, in terms of kg.

Input

Your program should be able to handle multiple queries.

The first line of input will be a single integer, TC.

The following TC lines of input will consists of one query each.

Each query consists of 2 integers, P and Q which denotes the range of fishes Rar the cat bought.

For 100% of the testcases, 1 ≤ TC ≤ 100000 and 2 ≤ P ≤ Q ≤ 1000000.

For 60% of the testcases, 1 ≤ TC ≤ 10000 and 2 ≤ P ≤ Q ≤ 10000.

For 30% of the testcases, TC = 1 and 2 ≤ P ≤ Q ≤ 1000.

Output

For each query, output a single integer on a line which denotes the number of fishes Rar the cat can use to cook the highest quality fish soup.

Refer to the Sample Output for more details.

Contest

For this question only, all the testcases will be made public (you will know your score). Please work on improving it (:

Sample Input

3
2 3
2 4
3 3

Sample Output

2
2
1

Tags

Number Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100100.5s1024MBAverage
2010.5s1024MBAverage

Judge Compile Command

g++-8 ans.cpp -o countfishes -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.