Yet Another Cute Girl
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef doesn't love math anymore. He loves Sasha. Sashen'ka is cute.
Chef goes on a date with her. Flowers are boring, while numbers are not. He knows that most of all this girl loves numbers, that's why he is going to bring ribbon with numbers L, L+1, L+2, ..., R written on it.
Sasha thinks that numbers with prime number of divisors are special. That's why she is going to kiss boy for each such number he will bring.
Now Chef wonder how many times he will be kissed by Sashen'ka ?
InputThe first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two number L, R.
OutputFor each test case, output a single line containing answer for corresponding test case.
- 1 ≤ T ≤ 5
- 1 ≤ L ≤ R ≤ 1012
- 0 ≤ R-L ≤ 106
Input: 1 1 10 Output: 6
Example case 1. Numbers 2,3,4,5,7,9 are special.
|Tags||ballon_ziq, easy, nov13, prime-factor, sieve|
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.