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 <= 10¹⁸
• 20% dintre teste vor avea b-a < 10⁶
• 30% dintre teste vor avea b-a < 10¹²

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

Mihail-Cosmin Piţ-Rada

Colegiul Naţional "Traian" Drobeta Turnu Severin

cosmin.pit@gmail.com