The Little Elephant loves numbers. 

He has a positive integer x. The Little Elephant wants to find the number of positive integers d, such that d is the divisor of x, and x and d have at least one common (the same) digit in their decimal representations. 

Help the Little Elephant to find the described number.

Input

A single line contains a single integer x (1 ≤ x ≤ 109).

Output

In a single line print an integer — the answer to the problem.

Examples

Input

1


Output

1


Input

10


Output

2
import math


class CodeforcesTask221BSolution:
    def __init__(self):
        self.result = ''
        self.x = 0

    def read_input(self):
        self.x = int(input())

    def process_task(self):
        if self.x == 1:
            self.result = "1"
        else:
            numix = 1
            repo = str(self.x)
            if "1" in repo:
                numix += 1
            for x in range(2, int(math.sqrt(self.x)) + 1):
                if x < self.x:
                    if not self.x % x:
                        #print(x, self.x // x)
                        have = False
                        for c in str(x):
                            if c in repo:
                                have = True
                                break
                        if have:
                            numix += 1
                        if self.x // x != x:
                            have = False
                            for c in str(self.x // x):
                                if c in repo:
                                    have = True
                                    break
                            if have:
                                numix += 1
            self.result = str(numix)

    def get_result(self):
        return self.result


if __name__ == "__main__":
    Solution = CodeforcesTask221BSolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())
