You, being free in semester, decide to do a side job to earn some money. You approach the recruiter Makkunda for job and he gives you a job but with a very weird pay policy. He says that if you work from day 1 to day n, he will pay you on each day which is a prime number and the pay on that day will be equal to the sum of digits of that prime number. You accept the job and are very excited to know how much you will earn from day l to day r and being a legendary coder you obviously write a program for it.

So, you decide to write a program that accepts q queries. For each query, given $l, r$ it finds the money you earn from day l to day r (assuming you work on all the days,which is nothing but the sum of sum of digits of all the prime numbers in the range $l,r$ both inclusive) . For each query you have to output the answer in a new line

By convention 1 is not a prime number.

Input:

First line contains single integer q followed by q lines where the $i^{th}$ line contains 2 space separated integers $l,r$ denoting the $l, r$ for the $i^{th}$ query.

Output:

Print q lines where the $i^{th}$ line is the answer to the $i^{th}$ query.

Constraints:

1. $0 \leq q \leq 10^5$
2. $1 \leq l \leq r \leq 10^7$