Lucky Numbers

John recently arrived in Bucharest, Eastern Europe, for a regional contest. John is famous for his theory of lucky numbers, which is exactly why the contestants and spectators are so glad to see him.

According to his theory, among the digits 0–9 the digits 4 and 7 are lucky, and all other digits are not. A lucky number is a number whose decimal representation consists only of lucky digits (4 or 7). A great lucky number is a number that can be written as a product of one or more lucky numbers. A lucky number by itself is also considered a great lucky number (as a product of a single lucky number). For example, 47 ($47$), 49 ($7 \times 7$), and 112 ($4 \times 7 \times 7$) are all great lucky numbers.

Your task is to count the great lucky numbers that are between $A$ and $B$, inclusive. John gives you $A$ and $B$.

Here, a 'digit' means a single decimal digit (0–9), and a 'number' means a natural number.

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines contains two integers $A$ and $B$ separated by a space.

• $1 \le T \le 7777$
• $1 \le A \le B \le 10^{12}$

For each test case, print the number of great lucky numbers between $A$ and $B$, inclusive, one per line, for a total of $T$ lines.

When $A = 1$ and $B = 100$, the great lucky numbers are 4, 7, 16 ($4 \times 4$), 28 ($4 \times 7$), 44, 47, 49 ($7 \times 7$), 64 ($4 \times 4 \times 4$), 74, and 77.