#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;
bool prime (int x){ //функция для проверки простоты нечётного числа
bool pr=true;
for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;
return pr;
}
int main() {
vector <int> v,prime_v;
unordered_map <int,bool> prime_m;
int u,i,j,maxx=0;
while(cin>>u){
v.push_back(u);
maxx=max(maxx,u);//максимальное значение во входном потоке
}
for(i=3;i<=maxx;i+=2){
if(prime(i)){
prime_m[i]=true;
prime_v.push_back(i);
}
}
int *dp,k;
dp = new int [maxx+1];
for(i=0;i<=maxx;i++)dp[i]=0;
for(i=8;i<=maxx;i++){//динамика
if(i%2){
for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){
k=i-prime_v[j];
if(dp[k]){
dp[i]+=dp[k];
if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];
}
}
}
else{
for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){
k=i-prime_v[j];
if(prime_m[k])dp[i]++;
}
}
if(i%2)dp[i]/=3;
}
for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPGNtYXRoPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKYm9vbCBwcmltZSAoaW50IHgpeyAvL9GE0YPQvdC60YbQuNGPINC00LvRjyDQv9GA0L7QstC10YDQutC4INC/0YDQvtGB0YLQvtGC0Ysg0L3QtdGH0ZHRgtC90L7Qs9C+INGH0LjRgdC70LAKCWJvb2wgcHI9dHJ1ZTsKCWZvcihpbnQgaT0yOyBpPD1zcXJ0KHgpO2krKylpZighKHglaSkpcHI9ZmFsc2U7CglyZXR1cm4gcHI7Cn0KaW50IG1haW4oKSB7Cgl2ZWN0b3IgPGludD4gdixwcmltZV92OwoJdW5vcmRlcmVkX21hcCA8aW50LGJvb2w+IHByaW1lX207CglpbnQgdSxpLGosbWF4eD0wOwoJd2hpbGUoY2luPj51KXsKCQl2LnB1c2hfYmFjayh1KTsKCQltYXh4PW1heChtYXh4LHUpOy8v0LzQsNC60YHQuNC80LDQu9GM0L3QvtC1INC30L3QsNGH0LXQvdC40LUg0LLQviDQstGF0L7QtNC90L7QvCDQv9C+0YLQvtC60LUKCX0KCWZvcihpPTM7aTw9bWF4eDtpKz0yKXsKCQlpZihwcmltZShpKSl7CgkJCXByaW1lX21baV09dHJ1ZTsKCQkJcHJpbWVfdi5wdXNoX2JhY2soaSk7IAoJCX0KCX0KCWludCAqZHAsazsKCWRwID0gbmV3IGludCBbbWF4eCsxXTsKCWZvcihpPTA7aTw9bWF4eDtpKyspZHBbaV09MDsKCWZvcihpPTg7aTw9bWF4eDtpKyspey8v0LTQuNC90LDQvNC40LrQsAoJCWlmKGklMil7CgkJCWZvcihqPTA7KGo8cHJpbWVfdi5zaXplKCkpJiYocHJpbWVfdltqXTxpKTtqKyspewoJCQkJaz1pLXByaW1lX3Zbal07CgkJCQlpZihkcFtrXSl7CgkJCQkJZHBbaV0rPWRwW2tdOwoJCQkJCWlmKChwcmltZV9tW2stcHJpbWVfdltqXV0pJiYoKGstcHJpbWVfdltqXSkhPXByaW1lX3Zbal0pKS0tZHBbaV07CgkJCQl9CgkJCX0KCQl9CgkJZWxzZXsKCQkJZm9yKGo9MDsoajxwcmltZV92LnNpemUoKSkmJihwcmltZV92W2pdPChpLzIpKTtqKyspewoJCQkJaz1pLXByaW1lX3Zbal07CgkJCQlpZihwcmltZV9tW2tdKWRwW2ldKys7CgkJCX0KCQl9CgkJaWYoaSUyKWRwW2ldLz0zOwoJfQoJZm9yKGk9MDtpPHYuc2l6ZSgpO2krKyljb3V0PDxkcFt2W2ldXTw8J1xuJzsKCXJldHVybiAwOwp9