#include<iostream>

#include<math.h>

#include<memory.h>

using namespace std;

int dp[200],a[200];

int main()

{

	int n,i,j,m;

	cin>>n;

	while(n--)

	{

		memset(dp,0,sizeof(dp));

		memset(a,0,sizeof(a));

		int p=0;

		dp[0]=1;

		cin>>m;

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

		{

			int k=sqrt(i);

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

				if(i%j==0)

					break;

				if(j>=k+1)

					a[p++]=i;

		}

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

			for(j=a[i];j<=m;j++)

				dp[j]=dp[j]+dp[j-a[i]];

			cout<<dp[m]<<endl;

	}

  	return 0;

}