Без девяток

면접 대비

시간 제한2초메모리 제한1024 MB

요약

l과 r 사이에서 십진수 표현에 9가 들어가지 않는 수의 개수를 센다. l과 r 자체에는 9가 없고 r은 10^15까지 커질 수 있다.

난이도: 보통10점 중 5점
유형: 수학, 조합론, 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

Каждый вечер Человек-Паук садится за свой компьютерный стол и записывает на лист бумаги все числа в диапазоне от $l$ до $r$ включительно. К сожалению, Человек-Паук очень не любит цифру девять. Поэтому он всегда пропускает числа, в которых есть цифра девять.

Ваша задача --- по заданным $l$ и $r$ определить, сколько чисел Человек-Паук запишет на лист бумаги, если учитывать, что лист вмещает неограниченное количество чисел.

입력

В единственной строке расположены два числа $l$ и $r$ --- границы диапазона чисел, которые Человек-Паук будет записывать ( $1 \le l \le r \le 10^{15}$ ). Обратите внимание, так как Человек-Паук не любит девятки, гарантируется, что $l$ и $r$ также не содержат девяток!

출력

В единственной строке выведите ответ --- количество записанных на листе чисел.

힌트

В первом тестовом примере из отрезка $\[1, 10]$ Человек-Паук выпишет все числа, кроме числа $9$ .

Во втором тестовом примере Человек-Паук выпишет все числа, кроме $89, 90, 91, \ldots, 99$ .

예제2

예제 1
입력
```
1 10
```
예상 출력
```
9
```
예제 2
입력
```
80 100
```
예상 출력
```
10
```