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.
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 <= 10⁵
2 <= N <= 10⁴

Subtask 1:
T = 100, 2 <= N <= 1000 - 20 points

Subtask 2:
T = 10⁵, 2 <= N <= 10⁴ - 80 points