#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define maxv 100
#define maxe 20000
using namespace std;
int n,m,d,x,y,z,g[maxv],nume=1,s1,s2,ans=0;
struct edge
{
    int v,f,nxt;
}e[maxe];
bitset <maxv> dp1[maxv][(1<<10)+1][2],dp2[maxv][(1<<10)+1][2];
bitset <1030> vvv[maxv],kr;
bool vis[(1<<20)+1],arr[maxv][15];
void addedge(int u,int v,int f)
{
    e[++nume].v=v;e[nume].f=f;
    e[nume].nxt=g[u];g[u]=nume;
}
void dp1s()
{
    for (register int i=1;i<=s1;i++)
    {
        for (register int j=1;j<=n;j++)
            for (register int k=0;k<(1<<s1);k++)
                dp1[j][k][i&1].reset();
        for (register int j=1;j<=n;j++)
            for (register int k=g[j];k;k=e[k].nxt)
            {
                int v=e[k].v,f=e[k].f,rr=i&1;
                for (register int s=0;s<(1<<(i-1));s++)
                    dp1[j][(s<<1)|f][rr]|=dp1[v][s][rr^1];
                arr[j][i]|=arr[v][i-1];
            }
    }
}
void dp2s()
{
    for (register int i=1;i<=s2;i++)
    {
        for (register int j=1;j<=n;j++)
            for (register int k=0;k<(1<<s2);k++)
                dp2[j][k][i&1].reset();
        for (register int j=1;j<=n;j++)
            for (register int k=g[j];k;k=e[k].nxt)
            {
                int v=e[k].v,f=e[k].f,rr=i&1;
                for (register int s=0;s<(1<<(i-1));s++)
                    dp2[j][(s<<1)|f][rr]|=dp2[v][s][rr^1];
            }
    }
}
void comb()
{
    for (register int i=1;i<=n;i++)
        for (register int j=0;j<(1<<s1);j++)
            if (dp1[i][j][s1&1].count())
                vvv[i][j]=1;
    for (register int i=1;i<=n;i++)
        for (register int j=0;j<(1<<s2);j++)
        {
            if (dp2[i][j][s2&1].count())
            {
                kr.reset();
                for (register int k=1;k<=n;k++) 
                    if (dp2[i][j][s2&1][k])
                        kr|=vvv[k];
                for (register int k=0;k<(1<<s1);k++)
                {
                    if (kr[k])
                        vis[k<<s2|j]=true;
                }
            }
        }                                                                                                                                                                                                                                                                                                                          
}
int main()
{ 
    scanf("%d%d%d",&n,&m,&d);
    for (register int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);addedge(y,x,z);    
    }    
    s1=d/2;s2=d-s1;arr[1][0]=true;dp1[1][0][0][1]=1;
    dp1s();
    for (register int i=1;i<=n;i++)
        if (arr[i][s1]) dp2[i][0][0][i]=1;
    dp2s();
    comb();
    for (register int i=0;i<(1<<d);i++) ans+=vis[i];
    printf("%d\n",ans);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 2050
#define inf 2000000
using namespace std;
int n,m,k,no[maxn][maxn],so[maxn][maxn],map[maxn][maxn],x[maxn],y[maxn],ans[maxn],dp[maxn][maxn];
int q1[maxn],h1,t1,q2[maxn],h2,t2;
char s[maxn];
void get_table()
{
    for (int j=1;j<=m;j++)
    {
        int ret=0;
        for (int i=1;i<=n;i++)
        {
            no[i][j]=ret;
            if (map[i][j]) ret=i;
        }
        ret=n+1;
        for (int i=n;i>=1;i--)
        {
            so[i][j]=ret;
            if (map[i][j]) ret=i;
        }
    }
}
void dp_()
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            if (!map[i][j]) dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
            else dp[i][j]=0;
            ans[k]=max(ans[k],dp[i][j]);
        }
}
bool check(int l,int x,int y)
{
    int lb=-1,rb=inf,ret=0;
    for (int i=y-1;i>=0;i--) if (map[x][i]) {lb=i+1;break;}
    for (int i=y+1;i<=m+1;i++) if (map[x][i]) {rb=i-1;break;}
    int left=max(lb,y-l+1),right=min(y,rb-l+1);h1=h2=1;t1=t2=0;
    for (int i=left;i<=left+l-1;i++)
    {
        while (h1<=t1 && no[x][i]>=no[x][q1[t1]]) t1--;q1[++t1]=i;
        while (h2<=t2 && so[x][i]<=so[x][q2[t2]]) t2--;q2[++t2]=i; 
    }
    for (int i=left;i<=right;i++)
    {
        ret=max(ret,so[x][q2[h2]]-no[x][q1[h1]]-1);
        while (h1<=t1 && q1[h1]<=i) h1++;
        while (h1<=t1 && no[x][i+l]>=no[x][q1[t1]]) t1--;q1[++t1]=i+l;
        while (h2<=t2 && q2[h2]<=i) h2++;
        while (h2<=t2 && so[x][i+l]<=so[x][q2[t2]]) t2--;q2[++t2]=i+l;
    }
    return ret>=l;
}
void ask()
{
    for (int i=k;i>=2;i--)
    { 
        map[x[i]][y[i]]=0;
        int ret=0;
        for (int j=1;j<=n;j++)
        {
            no[j][y[i]]=ret;
            if (map[j][y[i]]) ret=j;    
        } 
        ret=n+1;
        for (int j=n;j>=1;j--)
        {
            so[j][y[i]]=ret;
            if (map[j][y[i]]) ret=j;
        }
        int p=ans[i]+1;
        while (check(p,x[i],y[i]) && p<=min(n,m))
            p++;
        ans[i-1]=p-1;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for (int j=1;j<=m;j++)
        {
            if (s[j]==‘X‘) map[i][j]=1;
            else map[i][j]=0;
        }
    }
    for (int i=1;i<=n;i++) map[i][0]=map[i][m+1]=1;
    for (int i=1;i<=m;i++) map[0][i]=map[n+1][i]=1;
    for (int i=1;i<=k;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        map[x[i]][y[i]]=1;
    }
    get_table();
    dp_();
    ask();
    for (int i=1;i<=k;i++) printf("%d\n",ans[i]);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100500
using namespace std;
long long n,prime[maxn],tot=0,w[maxn][60],ans=0,mn[maxn],f,kr=0;
bool vis[maxn];
void get_table()
{
    for (long long i=2;i<=maxn-500;i++)
    {
        if (!vis[i]) prime[++tot]=mn[i]=i;
        for (long long j=1;i*prime[j]<=maxn-500;j++)
        {
            vis[i*prime[j]]=true;mn[i*prime[j]]=prime[j];
            if (i%prime[j]) continue;break;
        }
    }
    for (long long i=2;i<=maxn-500;i++)
    {
        long long ret=-1,x=i;
        while (x!=1)
        {
            if (mn[x]!=ret) {ret=mn[x];w[i][0]++;w[i][w[i][0]]=mn[x];}
            x/=mn[x];
        }
    }
}
void dfs(long long now,long long top,long long ret,long long val,long long n)
{
    if (now==w[top][0]+1)
    {
        if (!ret) return;
        if (ret&1) kr+=n/val;else kr-=n/val;
        return;
    }
    dfs(now+1,top,ret,val,n);
    dfs(now+1,top,ret+1,val*w[top][now],n);
}
void ask(long long n,long long val) {kr=0;dfs(1,val,0,1,n);}
int main()
{
    scanf("%lld",&n);
    get_table();
    long long top=sqrt(n);
    for (long long i=2;i<=top;i++)
    {
        ask(n/i,i);ans+=(n/i)-kr;
        ask(i,i);ans-=i-kr;
    }
    printf("%lld\n",ans);
    return 0;
}