A k-digit positive integer (written with no leading zeros) is called a titanic
number if exactly one of its sub-strings is divisible by k.

For example, 56712 is a titanic number. Among all its sub-strings,
5, 6, 7, 1, 2, 56, 67, 71, 12, 567, 671, 712, 5671, 6712, 56712, only 5 is
divisible by 5.

However, 163 is not a titanic number because 3 of its sub-strings, 3, 6 and 63
are divisible by 3.

Now, let the function T(N) be the number of titanic numbers less than N.

Input:
A list of positive integers, N such that 0 ≤ N ≤ 10^15. (One per line)
Stop when you encounter the number 0.

Output:
The values of T(N) for each of the values of N. (One per line)

PLEASE SUBMIT YOUR SOLUTIONS AGAIN

SAMPLE INPUT
10
6
0

SAMPLE OUTPUT
9
5

见题面

见题面