/** @Cain*/
const int S =
20;
inline ll mult_mod(ll a, ll b, ll m)
{
ll c = a*b-(ll)((
long double)a*b/m+
0.5)*m;
return c<
0 ? c+m : c;
}
ll pow_mod(ll a,ll b,ll m)
{
ll res =
1;
while (b)
{
if (b &
1) res = mult_mod(res, a, m);
a = mult_mod(a, a, m);
b >>=
1;
}
return res;
}
bool miller_rabin(ll n)
{
if (!(n&
1))
return n ==
2;
ll u=n-
1,t=
0;
while(u%
2==
0) u/=
2,++t;
for (
int i =
0; i < S; ++i){
ll a = rand()%(n-
2)+
2;
ll x = pow_mod(a, u, n);
for (ll j =
0; j < t ; j++){
ll y = mult_mod(x, x, n);
if (x ==
1 && y != n-
1 && y !=
1)
return false;
x = y;
}
if (x !=
1)
return false;
}
return true;
}
void solve()
{
srand(time(
0));
int t;
while(~scanf(
"%d",&t)){
int ans=
0;
for(
int i=
1;i<=t;i++){
ll x; cin >> x;
if(miller_rabin(x)) ans++;
}
cout<<ans<<endl;
}
}
