All submissions for this problem are available.
The New Zealand government is super-excited about the Cricket World Cup 2015 happening in their country. Hence, it has decided to conduct a census on cricket to find out how many people are interested in the sport, etc.
The statistics obtained are given to us as a range of numbers from A to B (inclusive). In these statistics, the government is interested in some particular numbers called "Kiwi Numbers".
A number is called a Kiwi Number if it has a prime number of distinct factors. A prime number N has exactly two divisors, 1 and N.
Can you help the government by calculating the number of Kiwi numbers in the given range?
The first line contains the number of test cases T.
Each of the next T lines contains two space separated numbers A and B.
For each test case, output the required answer on a separate line.
1 <= T <= 100
2 <= A <= B <= 1000000000
B - A <= 200000
For the first case, the Kiwi numbers are 2, 3, 4, 5, 7, 9.
|Tags||amr14ros, easy-medium, murdocc007, number-theory, seive|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.