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 sys, math
def rs():
    return sys.stdin.readline().strip()
def ri():
    return int(sys.stdin.readline().strip())
def ras():
    return sys.stdin.readline().strip().split()
def rai():
    return map(int,sys.stdin.readline().strip().split())
def main():
    x = ri()
    xx = list(str(x))
    def checkn(y):
        yy = list(str(y))
        for j in yy:
            if j in xx:
                return True
        return False

    count = 0
    if x==1:
        return 1
    for i in xrange(1, int(math.sqrt(x))+1):

        if not(x%i):
            if checkn(i):
                count+=1

            if checkn(x/i) and i!=x/i:
                count+=1

    return count



if __name__ == "__main__":
    print main()