I have came across a coding problem. I am unable to solve the problem. Can anyone help me out:

**PROBLEM STATEMENT**

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. primeprime e.g. 4, 27, etc.

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

*.*

**N****Output Format:**

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

**Constraints:**

* 1* <=

*<=*

**T**

**105***<=*

**2***<=*

**N**

**104****Subtask 1:**

* T* =

*,*

**100***<=*

**2***<=*

**N***- 20 points*

**1000****Subtask 2:**

* T* =

*,*

**105***<=*

**2***<=*

**N***- 80 points*

**104****SAMPLE INPUT**

2

6

3

**SAMPLE OUTPUT**

2

1

**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