#include<bits/stdc++.h>
#define ll long long
#define N ((int)1e6 + 5)
#define MOD ((int)1e9 + 7)
#define MAX ((int)1e9 + 7)
#define MAXL ((ll)1e18 + 7)
#define MAXP ((int)1e3 + 7)
#define thr 1e-8
#define pi acos(-1)  /// pi = acos ( -1 )
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define endl "\n"

using namespace std;

int isPrime[N/32 + 2];

bool IsPrime(int num) /// returns 1 for prime
{
    if(num == 2) return 1;
    if((num & 1) == 0)  return 0;
    int idx  = num >> 5 , bit = num & 31;
    if( ( isPrime[idx] & (1<<bit) ) != 0 ) return 0;
    else return 1;
}

vector < int > Sieve(int n)
{
    for(int i = 3; i * i <= n ; i += 2){
        if(IsPrime(i)){
            for(int j = i * i ; j <= n ; j += i<<1){
                int idx = j >> 5 , bit = j & 31;
                isPrime[idx] = isPrime[idx] | (1<<bit);
            }
        }
    }
    vector < int > prime;
    prime.push_back(2);
    for(int i = 3 ; i <= n ; i += 2){
        if(IsPrime(i)) prime.push_back(i);
    }
    return prime;
}

bool IsZeroDigit(int num)
{
    while(num > 0){
        if(num % 10 == 0) return true;
        num /= 10; /// num = 123056 -> 12305 -> 1230
    }
    return false;
}

bool IsSuffixPrime(int num)
{
    for(int mod = 10 ; ; mod = mod*10){
        int suffix = num % mod;
        if(IsPrime(suffix) == 0) return false;
        if(suffix == num) return true;
    }
}

int arr[N];



int main()
{
    /// problem: https://www.spoj.com/problems/VECTAR8/en/
    vector < int > prime = Sieve(1e6);
    for(int p:prime){
        if(IsZeroDigit(p) == false && IsSuffixPrime(p) == true){
            arr[p] = 1;
        }
    }
    for(int i = 1 ; i <= 1e6 ; i++) arr[i] += arr[i-1];
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<arr[n]<<endl;
    }
    return 0;
}