#include <bits/stdc++.h>
using namespace std;
int exp(int a,int n,int mod){
if(n==0) return 1;
int r;
r=exp(a,int(n/2),mod);
r=(r*r)%mod;
if(n%2==1) r=(r*a)%mod;
return r;
}
bool witness(int a,int n){
int t=0;
int u=n-1;
while(u%2==0){
u/=2;
t++;
}
int x[t];
x[0]=exp(a,u,n);
for(int i=1; i<t; i++){
x[i]=(x[i-1]*x[i-1])%n;
if(x[i]==1 && x[i-1] != 1 && x[i-1] !=n-1) return true;
if(x[t-1]!=1) return true;
return false;
}
}
int main(){
int ans=0;
for(int i=1; i<57; i++){
if(witness(i,57)) ans++;
}
cout<<ans<<endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgZXhwKGludCBhLGludCBuLGludCBtb2QpewogICAgaWYobj09MCkgcmV0dXJuIDE7CiAgICBpbnQgcjsKICAgIHI9ZXhwKGEsaW50KG4vMiksbW9kKTsKICAgIHI9KHIqciklbW9kOwogICAgaWYobiUyPT0xKSByPShyKmEpJW1vZDsKICAgIHJldHVybiByOwp9CmJvb2wgd2l0bmVzcyhpbnQgYSxpbnQgbil7CiAgICBpbnQgdD0wOwogICAgaW50IHU9bi0xOwogICAgd2hpbGUodSUyPT0wKXsKICAgICAgICB1Lz0yOwogICAgICAgIHQrKzsKICAgIH0KICAgIGludCB4W3RdOwogICAgeFswXT1leHAoYSx1LG4pOwogICAgZm9yKGludCBpPTE7IGk8dDsgaSsrKXsKICAgICAgICB4W2ldPSh4W2ktMV0qeFtpLTFdKSVuOwogICAgICAgIGlmKHhbaV09PTEgJiYgeFtpLTFdICE9IDEgJiYgeFtpLTFdICE9bi0xKSByZXR1cm4gdHJ1ZTsKICAgICAgICBpZih4W3QtMV0hPTEpIHJldHVybiB0cnVlOwogICAgICAgIHJldHVybiBmYWxzZTsKCiAgICB9Cn0KaW50IG1haW4oKXsKICAgIGludCBhbnM9MDsKICAgIGZvcihpbnQgaT0xOyBpPDU3OyBpKyspewogICAgICAgIGlmKHdpdG5lc3MoaSw1NykpIGFucysrOwogICAgfQogICAgY291dDw8YW5zPDxlbmRsOwp9Cg==