Project Euler #254: Sums of Digit Factorials

_{This problem is a programming version of Problem 254 from projecteuler.net}

Define as the sum of the factorials of the digits of . For example, .

Define as the sum of the digits of . So .

Define to be the smallest positive integer such that . Though is , is also , and it can be verified that is .

Define as the sum of the digits of . So .

Further, it can be verified that is and is .

What is ? As the number can be large, print it modulo .

Input Format

The first line of each test file contains a single integer , which is the number of queries per test file. lines follow, each containing two integers separated by a single space: and of the corresponding query.

Constraints

Output Format

Print exactly lines, each containing a single integer, which is the answer to the corresponding query.

Sample Input 0

2
3 1000000
20 1000000

Sample Output 0

8
156

Explanation 0

, and . .