Trol
Stjepan recibió recientemente su licenciatura en matemáticas de la Universidad de Zagreb. Naturalmente, sus padres están muy orgullosos y han decidido regalarle todos los números enteros positivos no superiores a \(2 ^{60}\). Para mantenerlos a salvo, rápidamente almacenó todos esos números en un Array \(A\), de modo que \(Ai = i\). Su celoso amigo Marin decidió hacerle una broma reemplazando repetidamente cada elemento de \(A\) con la suma de sus dígitos hasta que todos los elementos de \(A\) consistieran en un solo dígito. Por ejemplo, el valor inicial del elemento 197avo de A era 197. Marin primero cambió ese valor a \(1 + 9 + 7 = 17\) y luego cambió su valor nuevamente a \(1 + 7 = 8\). Stjepan está devastado y le ruega a Marin que devuelva su matriz a su estado inicial. Desafortunadamente, Marin no hará eso hasta que Stjepan responda correctamente a sus preguntas Q: "¿Cuál es la suma de los números del l-ésimo al r-ésimo elemento de A?". ¡Ayuda a Stjepan a responder esas consultas!
Entrada
La primera linea contiene un entero Q \(Q (1≤Q≤100)\) . Las siguientes \(Q\) lineas contienen dos enteros li y ri \((1≤li≤ri≤2^{60})\), que es los dos valores de la pregunta de Marin
Salida
Las respuestas a las preguntas de Marin. Cada respuesta en una línea separada y en el orden de las preguntas.
Ejemplo de Entrada 1
1
1 5Ejemplo de Salida 1
15Ejemplo de Entrada 2
2
9 13
44 45Ejemplo de Salida 2
19
17Ejemplo de Entrada 3
1
1998 2018Ejemplo de Salida 3
102Explicacion
En el ejemplo 2:
\(1a pregunta → A9=9, A10=1+0=1, A11=1+1=2, A12=1+2=3, A13=1+3=4 . A9+A10+A11+A12+A13=9+1+2+3+4=19.\)
\(2a pregunta → A44=4+4=8, A45=4+5=9. A44+A45=8+9=17.\)
Comentaris
Para empezar a hacer el problema os recomiendo que os hagais el array "reordenado" del 1 al 30 a ver si veis algo.