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 %I64d specifier.
Output
On a single line print a single integer — the answer to the problem.
Examples
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.
题意：
求l~r有多少个数字，满足首位和末位相同。
思路：
稍微有点恶心的数位模拟（学弟秒了，tql）
假设当前数字为 axxxxxb，假设a≤b，那么中间的xxxxx都可以算上，如果a>b，则中间的xxxxx可以算上，但是要减一。
最后再枚举其他首尾位置的数字，保证枚举的要小于原来的数字。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include <map>
#include <unordered_map>using namespace std;
typedef unsigned long long ll;const int maxn = 2e5 + 7;ll P[20];
int num[20];ll get(ll x) {if(x == 0) return 0;ll res = 0;int cnt = 0;ll tmp = x;while(tmp) {num[++cnt] = tmp % 10;tmp /= 10;}if(cnt == 1) {return x;}tmp = 0;for(int i = cnt - 1;i >= 2;i--) {tmp = tmp * 10 + num[i];}if(num[cnt] <= num[1]) {res += tmp + 1;x -= num[1] - num[cnt];} else {if(tmp != 0) {res += tmp;}}for(ll a = 1;a <= 9;a++) { //首位末位for(ll k = 0;k <= cnt - 2;k++) { //中间位数ll now = a * P[k + 1] + P[k + 1] - 10 + a;if(now < x) {res += P[k];}}}res += 9;return res;
}int main() {P[0] = 1;for(int i = 1;i <= 19;i++) P[i] = P[i - 1] * 10;ll l,r;scanf("%llu%llu",&l,&r);printf("%llu\n",get(r) - get(l - 1));return 0;
}
//76843