흥미로운 수

바샤는 어린 수학자입니다. 아버지는 바샤에게 자신의 어린 시절 이야기를 자주 들려줍니다. 특히 많은 또래 아이들처럼 아버지가 우표를 모으던 이야기가 많습니다. 우표마다 사연이 있었고, 아버지는 그 사연들을 세세한 부분까지 기억합니다. 가장 흥미로운 이야기는 '희귀 자동차' 시리즈 우표를 어떻게 구했는지에 관한 것입니다. 바샤는 이 이야기를 좋아했고, 직접 우표 모으기를 시작하기로 했습니다. 바샤는 희귀 자동차보다 수학을 더 좋아했기 때문에, 여러 가지 수가 적힌 우표를 모으기로 했습니다.

바샤는 끈기가 있어서 목표를 자주 이뤘습니다. 짧은 시간 안에 $a$부터 $b$까지 모든 수가 적힌 우표를 모았습니다. 우표마다 수가 정확히 하나씩 적혀 있습니다. 같은 수가 적힌 우표는 컬렉션에 남기지 않았으므로, 모든 우표에 적힌 수는 서로 다릅니다.

바샤는 우표마다 얽힌 사연도 아버지만큼 잘 기억합니다. 특히 십진 표기에서 같은 숫자가 연속으로 $k$개 이상 나타나는 수가 적힌 우표에 흥미로운 사연이 많았습니다. 바샤는 이런 우표를 흥미로운 우표라고 불렀습니다. 예를 들어 $k = 2$일 때 22, 111, 100, 556이 적힌 우표는 흥미롭고, 2, 121, 1212가 적힌 우표는 흥미롭지 않습니다.

$a$, $b$, $k$가 주어집니다. $a$부터 $b$까지의 수가 적힌 흥미로운 우표의 개수를 구하세요.

입력 파일에는 세 정수 $a$, $b$ ($1 \le a \le b \le 4 \cdot 10^{18}$)와 $k$ ($1 \le k \le 20$)가 주어집니다.

출력 파일에 문제의 답인 정수 하나를 출력하세요.

첫 번째 입력에서 흥미로운 우표는 11, 22, 33, 44, 55, 66, 77, 88, 99, 100입니다.

두 번째 입력에서 흥미로운 우표는 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 133입니다.