Gigel, un băiat foarte pasionat de puzzle-uri, a primit de ziua lui o cutie cu cifru, în interiorul căreia se află un cadou secret. Fiind curios din fire, el a tot încercat să descopere cifrul folosind fel de fel de combinaţii, însă niciuna nu s-a soldat cu succes. Aşadar s-a decis să citească cu atenţie instrucţiunile.
Astfel, Gigel a aflat că este o oarecare legătura între parola secretă şi palindromuri. El ştie că un palindrom este un număr ce se citeşte la fel, atât de la stânga la dreapta, cât şi de la dreapta la stânga. Gigel şi-a propus să încerce diverse strategii, însă a dedus că ar fi util mai întâi să afle câte palindroame se află într-un anumit interval [a, b] . Nefiind foarte bun la algoritmică, vă roagă pe voi să îl ajutaţi să răspundă eficient la această întrebare.
Cerinţă
Să se determine numărul de numere din intervalul [a, b] care au proprietatea de palindrom.
Date de intrare
Fişierul de intrare palindromuri.in conţine pe prima linie cele două numere naturale a şi respectiv b, reprezentând capetele intervalului de care este interesat Gigel.
Date de ieşire
Fişierul de ieşire palindromuri.out va trebui să conţină o singura linie pe care va fi scris numărul palindromurilor din intervalul [a, b].
Restricţii
1 <= a <= b <= 1018
20% dintre teste vor avea b-a < 106
30% dintre teste vor avea b-a < 1012
Exemple
palindromuri.in
palindromuri.out
Explicaţie
0 100
19
Palindromurile din intervalul dat sunt : 0 1 2 3 4 5 6 7 8 9 11 12 33 44 55 66 77 88 99