Armed Forces of the Confederacy of Independent Systems

"Our friends from the Trade Federation have pledged their support. And when their battle droids are combined with yours, we shall have an army greater than any in the galaxy. The Jedi will be overwhelmed. The Republic will agree to any demands we make."

―Count Dooku


The separatists have a huge army of droids. The droid army has a number of different types of droids, each optimized for a different objective.

The combat effectiveness(CE) of the type of droid is the largest integer such that for each integer , the sum of the power of each digit of is prime.

For example, the combat effectiveness of the type of droid is because is a prime number for . See the list below,







Here are prime numbers. But is not a prime.

Ideally, separatists would want to have combat effectiveness as high as possible. However, it turns out that if the combat effectiveness of a droid is or more, then it overloads and malfunctions. Therefore, the combat effectiveness of such droids becomes . For example: combat effectiveness of droids of type and is .

In this problem the goal is to find the sum of combat effectiveness of all types of droids in the range to (inclusive).

Input Format

The first line contains an integer denoting the number of test cases

The following lines will contain space sperated integers ,

Constraints:

Output Format

The output should be lines each containing a single integer.

Sample Input

2
1 5
7 12

Sample Output

3
2

Explanation

In the first range , the combat effectiveness of droids of type , and is . The combat effectiveness of others is .

In the second range , the combat effectiveness of droid of type is . combat effectiveness of droid of type is , and for type , it is . The combat effectiveness of others is .

  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score