Problem C: NB netizens

Problem C: NB netizens

Time Limit: 4 Sec  Memory Limit: 128 MB
Submit: 20  Solved: 11
[Submit][Status][Web Board]

Description

CC is a famous contestant in algorithm competitions. He is not only very handsome but also skilled in many techniques. So he has many fans (who adore him).

In order to help his fans improve the skills for competitions, CC has established an online chatting group and communicates with the fans about the techniques every day. However, some netizens do not work hard and always repeat meaningless messages. After CC sent an integer \(0\), some netizen will sent an integer \(1\) and then another sent \(2\) ... This annoys CC so he decides to kick some of the netizens out of the chatting group.

CC has infinite fans. After CC sent the integer \(0\), the netizens will sent \(1,2,3,4,...\), the positive integers one by one. Notice that each netizen will send an integer, and different netizens send different integers. CC considers those netizens who sends an integer contains no \(0\) or \(1\) digits in decimal (ignoring leading zeros) as NB netizens, and others are not NB. For example, A sends the integer \(3482\) so A is NB because there are no \(0\) or \(1\) in \(3,4,8,2\). B who sends \(402\) is not NB because there is a \(0\).

Now, CC kicks out those netizens who are not NB. After that, CC invites some of those remaining netizens in the group, who he thinks are also too naive, to attend exercise. He will give two positive integers \(L,R\) and invites those NB netizens who send an integer where the product of each digit of the integer is in \([L,R]\).

For example, given \(L=50, R=300\). Then, the netizen who sends \(567\) will be invited because he/she is NB and \(5\times 6\times 7=210\in[50,300]\). The netizen who sends \(255\) will also be invited. However, who sends \(328\) will not be invited.

CC wants to know how many NB netizens will be invited.

Input

The first line contains an integer \(T(1\leq T\leq 50)\), which is the number of test cases.

Then \(T\) lines follow. Each line contains two integers \(L,R (1\leq L\leq R\leq 2^{32}-1)\), representing a query.

Output

Output \(T\) lines. For each query, output an integer \(ans\) in one line, representing the number of invited NB netizens modulo \(10^9+7\).

Sample Input

4
3 6
4 9
2147483648 4294967295
5 5

Sample Output

7
13
793516016
1

HINT

[Submit][Status]