**Little Elephant and Interval

Little Elephant and Interval

The Little Elephant very much loves sums on intervals.

This time he has a pair of integers l and r (l ≤ r). The Little Elephant has to find the number of such integers x (l ≤ x ≤ r), that the first digit of integer x equals the last one (in decimal notation). For example, such numbers as 101, 477474 or 9 will be included in the answer and 47, 253 or 1020 will not.

Help him and count the number of described numbers x for a given pair l and r.

Input

The single line contains a pair of integers l and r (1 ≤ l ≤ r ≤ 1018) — the boundaries of the interval.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64dspecifier.

Output

On a single line print a single integer — the answer to the problem.

Sample test(s)

input

2 47

output

12

input

47 1024

output

98

Note

In the first sample the answer includes integers 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44.

--------------------------------------------editorial--------------------------

It is well-known that for such problem you need to write function F(x) which solves the problem for the interval 0..x, and the answer then is F(r) - F(l - 1).

now suppose no is 355675

so it is a 6 degit no soo all  1 to 5 degits numbers are already included in it , now comming to all 6 dfegit numbers which satisfy this condition and< = the current number

for that we  lets fix first no it can be 1,2,3 and for 1 ,2  rest all numbers (other than the last one can be any number ) soo 2*pow(10,len-2) added    len-2 since first and last no must remain same  ans 2* since for only 1 ,2 rest all len-2 numbers can be any number,

now try to fix second number it is 5 so for no 0 to 4 at this position lead to rest all numbers as any no 0 to 10 ,

similarly one by one fix all numbers ,,,,,,,,,,,

when we reach to second last number ie 7 since it is last (in the sence of removed corner numbers ) it can be any no ie in the rabnge 0 to 7,.

now 2 base cases 

if no is like 34567  computed ans  remain same

else if no is like 34562 computed answer decrease by1 since for the given combination 34562   no 34563 cant fromed which is computed in answer 

----------------------------------------code------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long int ulli;

ulli ans[100];

ulli val[100];

 ulli powe[100];

ulli solve(ulli num)

 {

  if(num<=9) return num;

   

  else if(num<=99)// if number is of <=2 degit 

   {

    ulli a=num%10;

    num/=10;

    ulli b=num%10;

    if(a>=b) return 9+b;

    else return 9+b-1;

  }

  

  else

  {

 

 

   ulli p1=0;

    ulli res=0;

  ulli dis=0;

  ulli p=num;

  ulli msb;

   

  while(p!=0)

   {

    msb=p%10;

    val[p1++]=msb;

      p/=10;

    dis++;

   

}

 

 

ulli  last=p1-1;

res+=ans[dis-1];

res+=(msb-1)*powe[dis-2];// fixing msb no as 1 to msb-1 lead to rest all 

                       // number except last one as 10 possibilities

dis-=2;// remainig no of  positions where number renaining to decide

p1-=2;// no oin the array position 

// 

while(dis!=0)

{

if(dis==1)//if only last no ramain to decide

 {

 

  res+=val[p1]+1;

  p1--;

  dis--;

 

  }

  else

  {

  res+=val[p1]*powe[dis-1];

  dis--;

  p1--;

  }

 

}

 

if(val[0]<val[last]) res--;

return res;

  }

 }

int main()

 {

   ans[1]=9;

      ans[2]=18;

     

       powe[0]=1;

       for(int i=1;i<23;i++) powe[i]=powe[i-1]*10;

       for(int i=3;i<=18;i++)

        {

        ans[i]=ans[i-1]+9*powe[i-2];

        

}

 

  ulli a,b;

  cin>>a>>b;

  cout<<solve(b)-solve(a-1)<<endl;

 

}