ID #123 · Colecția InfoAs · Operatori și expresii

Problema Lautari

Doi dintre lăutarii celebri ai România, _Will de pe Anglia_ și _Fane Taifunul_ , au dezvoltat un algoritm pentru a determina scorul melodiilor pe care le interpretează, în așa fel încât să poată determina ce melodii să poată cânta la evenimentele lor și să facă cel mai mare chef de chef. Pentru fiecare melodie se asociază un cod unic, număr natural nenul, iar cifra de control a acestui cod este de fapt scorul melodiei curente. Astfel, scorul este un număr între `1` și `9`. Algoritmul funcționează de _minune_ , dar Will de pe Anglia și Fane Taifunul au nevoie de ajutor pentru a determina foarte rapid pentru un set de melodii câte melodii au scorul maxim posibil `9`, pentru a putea face cea mai mare petrecere de la Mica Unire încoace. Will și Fane vor să se asigure că ești la zi cu termenii matematici, așadar îți spun că _cifra de control_ a unui număr natural este cifra care se obține însumând cifrele numărului, după care însumând cifrele sumei cifrelor numărului și așa mai departe până când ajungem la un număr de o cifră. De pildă, cifra de control a numărului `193` este `4`, pentru că `1 + 9 + 3 = 13`, iar `1 + 3 = 4`. ## Cerință Se dă numărul natural `q` și `q` perechi de numere `st` și `dr`. Pentru fiecare pereche `st` și `dr`, să se determine câte numere naturale din intervalul `[st, dr]` au cifra de control egală cu `9`. ## Date de intrare Fișierul de intrare `lautari.in` conține pe prima linie numărul natural `q`. Pe a doua linie se află câte două numere naturale `st` și `dr` separate printr-un spațiu, reprezentând cele `q` întrebări. ## Date de ieșire Fișierul de ieșire `lautari.out` conține `q` numere naturale, fiecare număr pe câte o linie separată, unde pe linia `i` se află răspunsul la cea de a `i`-a întrebare (`1 ≤ i ≤ q`). ## Restricții și precizări * `1 ≤ q ≤ 100.000` * `1 ≤ st ≤ dr ≤ 10<sup>16</sup>` ### Subtask 1 (14 puncte) * `1 ≤ q ≤ 100` * `1 ≤ st ≤ dr ≤ 1000` ### Subtask 2 (21 de puncte) * `1 ≤ q ≤ 10` * `1 ≤ st ≤ dr ≤ 100.000` ### Subtask 3 (65 de puncte) * Fără alte restricții