Problem J. Just Too Lucky

Author:ACM ICPC 2008-2009, NEERC, Northern Subregional Contest   Time limit:3 sec
Input   Memory limit:256 Mb
Output file:just.out  


Since mass transit was invented, people who buy tickets look for lucky ticket numbers. There are many notions of lucky tickets, for example sometimes tickets are considered lucky if the sum of first half of the digits is equal to the sum of the second half, sometimes the product is used instead of the sum, sometimes permutation of digits is allowed, etc.

In St Andrewburg integer numbers from 1 to n are used as ticket numbers. Bill considers a ticket lucky if its number is divisible by the sum of its digits. Help Bill to find the number of lucky tickets.

Input file format

The first line of the input file contains n.

Output file format

Output one number — the number of lucky tickets.


1 ≤ n ≤ 1012.

Sample tests

No. Input file ( Output file (just.out)

0.023s 0.005s 15