#include #define fr(i,n) for(int i=0;i<(n);++i) #define foor(i,a,b) for(int i=(a);i<=(b);++i) #define rf(i,n) for(int i=(n);i--;) #define roof(i,b,a) for(int i=(b);i>=(a);--i) #define elsif else if #define all(x) x.begin(),x.end() #define Sort(x) sort(all(x)) #define Reverse(x) reverse(all(x)) #define PQ priority_queue #define NP(x) next_permutation(all(x)) using namespace std; typedef vector vb; typedef vector vvb; typedef vector vi; typedef vector vvi; typedef long long ll; typedef vector< ll> vl; typedef vector vvl; typedef unsigned long long ull; typedef vector vu; typedef vector vvu; typedef double dbl; typedef vector vd; typedef vector vvd; typedef string str; typedef vector vs; typedef vector vvs; typedef pairpii; typedef vectorvpii; typedef mapmii; typedef pair< ll, ll>pll; typedef vectorvpll; typedef map< ll, ll>mll; typedef pairpdd; typedef vectorvpdd; typedef mapmdd; typedef pairpss; typedef vectorvpss; typedef mapmss; typedef pairpil; typedef vectorvpil; typedef mapmil; typedef pair< ll,int>pli; typedef vectorvpli; typedef map< ll,int>mli; typedef pairpdi; typedef vectorvpdi; typedef mapmdi; templatevector&operator<<(vector&v,const T t){v.push_back(t);return v;} templatemultiset&operator<<(multiset&m,const T t){m.insert(t);return m;} templateset&operator<<(set&s,const T t){s.insert(t);return s;} templatePQ,U>&operator<<(PQ,U>&q,const T t){q.push(t);return q;} templateistream&operator>>(istream&s,pair&p){return s>>p.first>>p.second;} templateistream&operator>>(istream&s,vector&v){fr(i,v.size()){s>>v[i];}return s;} templateostream&operator<<(ostream&s,const pairp){return s<ostream&operator<<(ostream&s,const vectorv){for(auto a:v){s<pairoperator+(paira,pairb){return {a.first+b.first,a.second+b.second};} templatepairoperator-(paira,pairb){return {a.first-b.first,a.second-b.second};} templatevoid print(T x){cout<void print(T x,U y){cout<void print(T x,U y,V z){cout<str to_string(const T&n){ostringstream s;s<vector>dijkstra(const vector>>E,const U s,const T inf){using P=pair;vector

d;fr(i,E.size()){d<,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstmap>dijkstra(map>>E,const U s,const T inf){using P=pair;mapd;for(pair>e:E){d[e.first]=P{inf,e.first};}PQ,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstT distsq(paira,pairb){return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);} templateT max(const vectora){T m=a[0];for(T e:a){m=max(m,e);}return m;} templateT min(const vectora){T m=a[0];for(T e:a){m=min(m,e);}return m;} templateT gcd(const T a,const T b){return a?gcd(b%a,a):b;} templateT gcd(const vectora){T g=a[0];for(T e:a){g=gcd(g,e);}return g;} templatevectorLIS(const vectorA){vi B;for(T a:A){auto it=lower_bound(all(B),a);if(it==B.end()){B<=0?a%m:~-m+~a%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:!!a;} ll inv(const ll x,const int p){return pow(x,p-2,p);} vpll fact(const int n,const int p){vpll v(n+1);v[0].first=1;foor(i,1,n){v[i].first=v[i-1].first*i%p;}v[n].second=inv(v[n].first,p);roof(i,n,1){v[i-1].second=v[i].second*i%p;}return v;} ll C2(const int n){return(ll)n*~-n/2;} ll sum(const vi a){ll s=0;for(int e:a){s+=e;}return s;} ll sum(const vl a){ll s=0;for(ll e:a){s+=e;}return s;} ll segsum(vl&s,int l,int r){l|=s.size()>>1;r|=s.size()>>1;if(l>r){return 0;}if(l==r){return s[l];}ll z=s[l]+s[r];for(;l>>1>1;l>>=1,r>>=1){l&1||(z+=s[l^1]);r&1&&(z+=s[r^1]);}return z;} void segadd(vl&s,int i,ll x){s[i|=s.size()>>1]+=x;for(;i>>1>=1;i>>=1){s[i>>1]=s[i]+s[i^1];}} ll BITsum(vl&B,int i){ll z=0;while(i>0){z+=B[i];i-=i&-i;}return z;} void BITadd(vl&B,int i,ll x){while(i>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;} vi primes(int n){vb b(n+1);vi p;foor(i,2,n){if(!b[i]){p< (int) // (int) / (int) => (int) int main(){cin.tie(0);ios::sync_with_stdio(false); int N; cin>>N; vi p=primes(2*N); vb isp=isprime(3*N); vi x(3*N); ll z=0; for(int c=3;p[c]<=N;++c){ int B=p[c-1]; foor(a,1,c-2){ ++x[p[a]+B]; } for(int ab=8;ab<2*B;ab+=2){ if(isp[ab+p[c]]){ z+=x[ab]; } } } print(z); return 0; }