Jack and Jones
Jack loves to play with numbers.One day he discovered that there's something called magic_values for a number. Magic_value of any number is sum of digit_sum of all unique prime factors(greater than 1) of a given number (For more clarification, see the explanation). Jack challenged his friend Jones to solve a problem based on magic_value of numbers. In this problem Jones have to count sum of magic_values for all numbers from L to R. But as we know that Jones does not like play with numbers so he needs your help to solve this problem. Note:digit_sum of a number is sum of digits of that number.
The first line contains an integer T, total number of testcases. Then next T lines contains two intergers L and R.
Print the required output with modulus 10**9+7 for each test case in a seperate line.
- 1 ≤ T ≤ 104
- 1 ≤ L ≤ R ≤ 106
- Subtask #1 [30 points]: 1 ≤ T≤ 103 & 1 ≤ L ≤ R ≤ 103
- Subtask #2 [70 points]: No additional constraints
Input: 2 1 3 11 12 Output: 5 7
In second test case: magic value for 11 (11) = 2 and magic value for 12 (2*2*3) = 5
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions