You have a function f(x) that returns the product of all the digits of that number.You will be given a number N. You have to find out how many x exists such that 0 ≤ x ≤ N and N ≤ f(x)

Input

There are several test cases in this problem. The input contains a positive integer N (1 ≤ N ≤ 10000). The input is terminated by end of file.

Output

Print the required answer on a separate line for each input.

Example

Input:
5
15

Sample Output
5
9

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology