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 .