You are Mario and are determined to rescue the princess. The princess is locked well inside the castle and you have to pass N gates to reach the princess. The villain, Bowser, being very smart, changed the locking system so that it becomes difficult to enter. The locking system is as follows :
- Two integers A and B are engraved on each gate.
- The sum of the digits of the prime numbers in the range [A, B] is the password to open the gate.
You have to open all the gates and rescue the princess.
The first line of the input contains an integer N denoting the number of gates.
N lines follow.
Each line contains two integers A and B of the ith gate.
For each gate, print an integer representing its password.
- 1 ≤ N ≤ 100
- 1 ≤ A ≤ B ≤ 109
- B-A ≤ 105
- Subtask #1[30 points] : 1 ≤ A ≤ B ≤ 1000
- Subtask #2[70 points] : Original constraints
Input: 2 2 10 13 14 Output: 17 4
Example case 1. 2 + 3 + 5 + 7 = 17
Example case 2. (1 + 3) = 4, since the only prime number is 13
|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, 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, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.