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 java.util.*;
import java.io.*;
import java.lang.*;



public class Main
{

  public static boolean check(ArrayList<Integer> a,int n)
  {
    int temp=n;
    while(temp!=0)
    {
      int rem=temp%10;
      if(a.contains(rem))
      {
        return true;
      }
      temp=temp/10;
    }
    return false;
  }

  public static void main(String[] args)
  {

    Scanner s=new Scanner(System.in);
  
    int n=s.nextInt();
    ArrayList<Integer> a= new ArrayList<>();
    int temp=n;
    if(n==1)
    {
      System.out.println(1);
      return;
    }
    while(temp!=0)
    {
      int rem=temp%10;
      a.add(rem);
      temp=temp/10;
    }
    int count=0;
    for(int i=1;i*i<=n;i++)
    {
      if(n%i==0)
      {
        if(check(a,i))
        {
          count++;
        }
        if(n/i!=i && check(a,n/i))
        {
          count++;
        }
      }


        
      
    }
    System.out.println(count);

  }
}
