Project Euler #134: Prime pair connection

_{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

Explanation

The following are the relevant values in the range :

Thus,