# Question Name:PRIME NUMBERS AGAIN

``````#include <iostream>
using namespace std;
int main()
{

int avi,b,i;
cin>>avi;
for(i=0;i<avi;i++) {
cin>>b;
if(b==1)
{
cout<<0<<endl;
}
if( b==3 || b==4 || b==2 || b==5 || b==7)
{
cout<<1<<endl;
}
if( b==6||b==9||b==8||b==10||b==21)
{
cout<<2<<endl;
}
}

return 0;
}``````
• Problem Description
Panda can do any problem anytime and anywhere. Panda is doing an extensive research on prime numbers. Milinda has got a question for Panda. The only way for Panda to impress Milinda is by solving this question.

Given a number N, find the minimum number of primatic numbers which sum upto N.

A primatic number refers to a number which is either a prime number or can be expressed as power of prime number to itself i.e. prime^prime e.g. 4, 27, etc.

Note: 8, 32, etc are not primatic numbers.

Input Format:
The first line will contain two integers: T, the number of test cases.
Each test case consists of a single integer N.

Output Format:
For each query output the minimum number of primatic numbers which can sum upto N.

Constraints:
1 <= T <= 10^5
2 <= N <= 10^4

T = 100, 2 <= N <= 1000 – 20 points

T = 10^5, 2 <= N <= 104 – 80 points
• Test Case 1
Input (stdin)2
6 3
Expected Output2
1
• Test Case 2
Input (stdin)11
4 2 1 3 5 7 6 9 8 10 21
Expected Output1
1
0
1
1
1
2
2
2
2
2