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