#include<bits/stdc++.h>
using namespace std;
char infile[100], outfile[100];
long long int S,n;
int g(int m){
    int i=2;
    while(i<m){
        if(m%i==0) return 0;
        i++;
    }
    return 1;
}
void f(int s, int m){
    long long int i;
    if(s==n and m==1){
        S++;
        return;
    }
    if(s>n) return;
    for(i=1;i<=3;i++){
        if(g(s+i)==1 and s+i >1){
            if(m==0) f(s+i,1);
        }else{
            f(s+i,m);
        }
    }
    return;
}
int main(){
    int i;
    for(i=1;i<=20;i++){
        n = i;
        S = 0;
        sprintf(infile, ".%d.in", i);
        freopen(infile, "w", stdout);
        printf("%lld\n", n);
        f(0,0);
        sprintf(outfile, ".%d.out", i);
        freopen(outfile, "w", stdout);
        printf("%lld\n",S);
    }
}