Poltu and Digit Product

You are given two integer $L$ and $R$. You have to find the summation of digit product of all number from $L$ to $R$ (inclusive).

Example of digit product:

The digit product of $154 = 1 × 5 × 4 = 20$.

The digit product of $1214 = 1 × 2 × 1 × 4 = 8$.

Input

The first line contains an integer $T$ ($1 \le T \le 100$), number of test cases.

Next T lines contain two integer $L$ and $R$($1 \le L \le R \le 10^{1000}$).

Output

For each test case print the case number and result mod $10^9 + 7$.

Sample

Input	Output
2 12 14 8 10	Case 1: 9 Case 2: 17