SOLVE

LATER

Prime Numbers Again

/

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

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

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

Panda is very sad since he is unable to solve the problem. Please help Panda in solving this problem.

**Input Format:**

The first line will contain two integers: ** T**, the number of test cases.

Each test case consists of a single integer

**Output Format:**

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

**Constraints:**

** 1** <=

**Subtask 1:**

** T** =

**Subtask 2:**

** T** =

Explanation

- The number 6 can be represented as 2 + 2 + 2, 3 + 3, etc. The smallest one among these is 3 + 3 consisting of 2 primatic numbers.
- The number 3 is itself primatic. Hence the answer is 1.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...