Lucky numbers
John has recently arrived in Bucharest for the South Eastern European Regional Contest. John is famous for his theory of lucky numbers. That’s why all the contestants and spectators are very happy.
According to that theory 4 and 7 are lucky digits, and all the other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation. A very lucky number is a number that can be expressed as a product of several lucky numbers. A lucky number by itself is considered to be very lucky. For example, numbers 47, 49, 112 are very lucky.
JYour task is to calculate the number of very lucky numbers that are not less than A and not greater than B. Of course, numbers A and B are given by John.
Constrains:
1 ≤ T ≤ 7777,
1 ≤ A ≤ B ≤ 1000000000000 (10^12).
Input:
4
1 2
88 99
112 112
1 100
Output:
0
0
1
10Hint:Very lucky numbers for the last case of the sample input are: 4, 7, 16, 28, 44, 47, 49, 64, 74 and 77.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.