This problem is a programming version of Problem 134 from projecteuler.net
Consider the consecutive primes and . It can be verified that is the smallest number such that the last digits are formed by whilst also being divisible by .
In fact, with the exception of and , for every pair of consecutive primes, , there exist values of for which the last digits are formed by and is divisible by . Let be the smallest of these values of .
Given and , find for every pair of consecutive primes with .
Input Format
The first line of input contains , the number of test cases.
Each test case consists of one line containing two integers, and .
Constraints
But in test cases worth 50% of the total points, .
Output Format
For each test case, output a single line containing a single integer, the answer for that test case.
Sample Input
1
5 20
Sample Output
4272
Explanation
The following are the relevant values in the range :
Thus,