/**********************************************************************\
|           _______  _     _____    ____   ___     _                   |
|          |___   _|(_)   / ___/   / _  | |   \   | |                  |
|              | |  | |  / /___   / /_| | | |\ \  | |                  |
|           _  | |  | | /___  /  /  __  | | | \ \ | |                  |
|           \ \| |  | | ___/ /  / /   | | | |  \ \| |                  |
|            \___/  |_|/____/  /_/    |_| |_|   \___|                  |
|                  Computer Science and Engineering                    |
|  Bangabandhu Sheikh Mujibur Rahman Science and Technology University |
|         devskill:jisancse||uva:jishan047||github:jisan047            |
\**********************************************************************/

                /********************\
                |                    |
                |    lets try.....   |
                |                    |
                \********************/

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

////Policy based data structure
//typedef tree<int, null_type, less<int>, rb_tree_tag,
//             tree_order_statistics_node_update> pbdsset;

///pre-processing
#define     gcd(a, b)       __gcd(a,b)
#define     lcm(a, b)       (a * b) / gcd(a, b)
#define     loop(i, n)      for(int i=0;i<n;i++)
#define     all(x)          x.begin(),x.end()
#define     mem(a, x)       memset(a,x,sizeof a)
#define     endl            '\n'
#define     ss              second
#define     ff              first
#define     TN              typename

///input functions
int Int(){int x;scanf("%d",&x);return x;}
long long Long(){long long x;scanf("%lld",&x);return x;}
double Double(){double x;scanf("%lf",&x);return x;}

///input functions shorting
#define Int Int()
#define Long Long()
#define Double Double()
#define Float Float()

///Constants
const int N = (int) 1e4 + 5;
const long long MOD = (int) 1e9 + 7;

///BitMask
int Set(int a, int x){return (a |= (1 << x));}
int Reset(int a, int x){return (a &= ~(1 << x));}
bool Isset(int a, int x){return (bool) (a & (1 << x));}

//Trying to do something.
//()()()()()()()()() ..... ()()()()()()()()()()()()
//~~~~~~~~~~~~~~~~~~~~~~Get Ready~~~~~~~~~~~~~~~~~~~~~

///debugger

///end

// loading..................

int lp[N];
vector<int> pr;
int dp[N][N];
int len;
int solution(int i, int p){
    if(i >= len) return -10000000;
    if(p < 0) return -10000000;
    if(!p)return 0;
    if(~dp[i][p]) return dp[i][p];
    return dp[i][p] = max(solution(i + 1, p), 1 + solution(i + 1, p - pr[i]));
}
int main(){
    mem(dp, -1);
    for(int i = 2; i < N; i++){
        if(lp[i] == 0){
            lp[i] = i;
            pr.push_back(i);
        }
        for(int j = 0; j < (int)pr.size() and pr[j] <= lp[i] and i * pr[j] < N; j++){
            lp[i * pr[j]] = pr[j];
        }
    }
    len = pr.size();
    int t = Int;
    while(t--){
        cout << max(0, solution(0, Int)) << endl;
    }
    return 0;
}