#include <bits/stdc++.h>
using namespace std;
#define int long long
int L,R,K,ans;
bool f[30],ps[200];
int p[20];
bool pr(int n)
{
    if(n<2)return 0;
    for(int i=2;i*i<=n;i++)if(n%i==0)return 0;
    return 1;
}
void dfs(int n,int pos,int u,int v,int x,int s,int pd)
{
    if(pos==(n+1)/2){
        int cur=x,sm=s,prd=pd,tmp=x;
        if(n%2)tmp/=10;
        while(tmp){
            int d=tmp%10;
            cur=cur*10+d;sm+=d;prd=(prd*d)%K;
            tmp/=10;
        }
        if(cur>=L&&cur<=R&&ps[sm]&&prd==0){
            if(n>=3&&!f[cur%10+(cur/10)%10+(cur/100)%10])return;
            ans++;
        }
        return;
    }
    for(int d=(pos==0);d<=9;d++){
        if(pos>0&&d==u)continue;
        if(pos>=2&&!f[v+u+d])continue;
        dfs(n,pos+1,d,u,x*10+d,s+d,(pd*d)%K);
    }
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    for(int x:{0,1,2,3,5,8,13,21})f[x]=1;
    for(int i=2;i<200;i++)if(pr(i))ps[i]=1;
    p[0]=1;
    for(int i=1;i<=18;i++)p[i]=p[i-1]*10;
    if(!(cin>>L>>R>>K))return 0;
    for(int i=1;i<=18;i++){
        if(p[i-1]>R)break;
        if(p[i]-1<L)continue;
        dfs(i,0,-1,-1,0,0,1);
    }
    cout<<ans<<"\n";
}