Arithmetic Digit Numbers 2

Count the integers from 1 to N, with N up to 10^18, whose decimal digits form an arithmetic sequence.

Medium5BacktrackingCombinatoricsMathNo attempts yetTime limit0.5sMemory limit512 MB

Problem

A positive integer XX is an arithmetic digit number when its digits, read from left to right, form an arithmetic sequence. An arithmetic sequence is a sequence in which the difference between two neighboring terms is always the same. A sequence of one or two terms satisfies that condition, so every one-digit number and every two-digit number is an arithmetic digit number.

Given NN, write a program that prints how many arithmetic digit numbers are at least 11 and at most NN.

Input

The first line contains a natural number NN that is at most 101810^{18}.

Output

Print on the first line the count of arithmetic digit numbers that are at least 11 and at most NN.