Profesor Đurić u poslednje vreme ima velikih problema sa svojim nestašnim đacima. Da bi ih smirio, odlučio je da im da, na prvi pogled, mnogo težak zadatak. U prošlosti su se često primenjivale takve mere smirivanja, i omiljen zadatak je bio sabiranje prvih 1000 brojeva. Ali, otkako je mali Gaus našao način da brzo izračuna taj zbir, profesori su morali da promene zadatak. I tako je prof. Đurić smislio sledeće: daće đacima nenegativne cele brojeve A i B, i tražiće od njih da mu kažu koliko brojeva iz intervala [A,B] (tj. svi brojevi veći ili jednaki od A i manji ili jednaki od B) ima paran zbir cifara (npr, zbir cifara broja 1234 je 1 + 2 + 3 + 4 = 10, dakle paran broj). Međutim, među đacima se nalazi i mali Draganče koji, poput malog Gausa, želi da što pre reši taj zadatak i nastavi da pravi probleme prof. Đuriću. Kako Draganče nije uspeo da nađe rešenje zadatka, pomoć je potražio od njegovih drugova, mladih programera.

Ulaz:

(Ulazni podaci se nalaze u datoteci gaus.in) U prvom redu tekstualne datoteke zapisani su brojevi A i B, odvojeni jednim razmakom.

Izlaz:

(Izlazne podatke upisati u datoteku gaus.out) U izlaznu datoteku ispisati samo jedan broj - koliko ima brojeva iz intervala [A,B] takvih da im je zbir cifara paran broj.

Ograničenja:

• 0 ≤ A ≤ B ≤ 2³⁰
• vremensko ograničenje za izvršavanje programa je 1 s.

Primer 1:

5 15

5

Primer 2:

16 20

3

// Gaus, Okruzno 2007
#include <cstdio>
#include <vector>
using namespace std;

vector<int> cifra;

long count(long n, bool paran, bool manje){
  if (n==-1){
    if (paran) return 1;
    else return 0;
  }
  else{
    long ret=0;
    
    if (manje){
      ret += 5*count(n-1,paran,true) + 5*count(n-1,!paran,true);
    }
    else{
      if (cifra[n]%2==0) ret += count(n-1, paran, false);
      else ret += count(n-1,!paran,false);
      
      if (cifra[n]>0){        
        int p=1 + (cifra[n]-1)/2;
        int np=(1 + cifra[n]-1)/2;        
      
        ret += p * count(n-1,paran,true);
        ret += np * count(n-1,!paran,true);
      }            
    }
    
    return ret;
  }
}


int main(){
  long A,B;
  
  FILE *f;
  f=fopen("gaus.10.in","r");
  fscanf(f,"%ld %ld",&A,&B);
  fclose(f);  

  long res=0;
  
  while (B>0){
    cifra.push_back(B%10);
    B/=10;
  }
  res+=count(cifra.size()-1,true,false);
  
  cifra.clear();
  A--;
  while (A>0){
    cifra.push_back(A%10);
    A/=10;
  }
  res-=count(cifra.size()-1,true,false);

    
  f=fopen("gaus.10.out","w");
  fprintf(f,"%ld\n",res);
  fclose(f);
  
  return 0;
}