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