4082 - Bobby and the Interesting Numbers

Created by Rubén Alcolea Núñez
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Bobby is a smart kid, but he always arrives late to class. That’s why, his professor wants to design a set of exercises in order to increase Bobby’s motivation for classes. Today, Bobby’s teacher decided to teach a lesson about interesting numbers. He is interested in counting interesting numbers within a given range.

A number is considered interesting if the number of digits 2 plus the number of digits 3 is equal to the number of digits 5 and there is at least a digit 2 or 3. For example, 2355 and 25 are interesting numbers, because they fulfill the definition of interesting number. Bobby asked your help to write a program to compute how many interesting numbers are there in the range [A, B]. The answer can be very large, so print it modulo 1000000007.
Bobby es un niño inteligente, pero siempre llega tarde a clase. Es por eso que su profesor quiere diseñar un conjunto de ejercicios para aumentar la motivación de Bobby en las clases. Hoy, el maestro de Bobby decidió dar una clase sobre números interesantes. Él está interesado en contar números interesantes dentro de un rango determinado.

Un número se considera interesante si el número de dígitos 2 más el número de dígitos 3 es igual al número de dígitos 5 y hay al menos un dígito 2 o 3. Por ejemplo, 2355 y 25 son números interesantes, porque cumplen el definición de número interesante. Bobby pidió tu ayuda para escribir un programa para calcular cuántos números interesantes hay en el rango [A, B]. La respuesta puede ser muy grande, así que imprímalo módulo 1000000007.
Bobby is a smart kid, but he always arrives late to class. That’s why, his professor wants to design a set of exercises in order to increase Bobby’s motivation for classes. Today, Bobby’s teacher decided to teach a lesson about interesting numbers. He is interested in counting interesting numbers within a given range.

A number is considered interesting if the number of digits 2 plus the number of digits 3 is equal to the number of digits 5 and there is at least a digit 2 or 3. For example, 2355 and 25 are interesting numbers, because they fulfill the definition of interesting number. Bobby asked your help to write a program to compute how many interesting numbers are there in the range [A, B]. The answer can be very large, so print it modulo 1000000007.

Input specification

The input contains in the first line the number of test cases 1 ≤ T ≤ 100. The following T lines have two integers A and B, 1 ≤ A ≤ B ≤ 10^50 representing the information of a given range.
La entrada contiene en la primera línea el número de casos de prueba 1 ≤ T ≤ 100. Las siguientes T líneas tienen dos enteros A y B, 1 ≤ A ≤ B ≤ 10^50 que representan la información de un rango determinado.
The input contains in the first line the number of test cases 1 ≤ T ≤ 100. The following T lines have two integers A and B, 1 ≤ A ≤ B ≤ 10^50 representing the information of a given range.

Output specification

For each test case, the output contains the amount of interesting numbers in the given range.
Para cada caso de prueba, la salida contiene la cantidad de números interesantes en el rango dado.
The input contains in the first line the number of test cases 1 ≤ T ≤ 100. The following T lines have two integers A and B, 1 ≤ A ≤ B ≤ 10^50 representing the information of a given range.

Sample input

3
1 100
10 1000
500 10000

Sample output

4
84
1160

Hint(s)