#include <iostream>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 int prime[];

 int c1[];

 int c2[];

 int num[];

 int l;

 void init()

 {

     int i,j;

     num[]=;

     num[]=;

     for(i=; i<=; i++)

         for(j=i*i; j<=; j+=i)

             num[j]=;

     for(i=; i<=; i++)

         if(!num[i])

             prime[l++]=i;   //素数表。。

 }

 int main()

 {

     init();

     int n,t,i,j,k;

     memset(c2,,sizeof(c2));

     for(i=; i<=; i+=)  //第一个素数是2，所以这里的增量是2.

         c1[i]=;

     for(i=; i<=; i++)

      {

          for(j=; j<=; j++)

         {

             for(k=; k+j<=; k+=prime[i])  //每次的添加都是第i个素数的值。

                 c2[k+j]+=c1[j];

         }

             for(j=; j<; j++)

             {

                 c1[j]=c2[j];

                 c2[j]=;

                  //printf("%d\n",c1[j]);

             }

      }

     cin>>t;

     while(t--)

     {

         cin>>n;

         cout<<c1[n]<<endl;

     }

     return ;

 }