3580번 - Just Too Lucky 다국어

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.

The first line of the input file contains n (1 ≤ n ≤ 10¹²).

Output one number — the number of lucky tickets.