Minimum Number of Stabs to Kill the King

You are given the initial health of a king represented by an integer N. Your task is to determine the minimum number of stabs required to reduce the king's health to zero, thereby killing the king.

Explanation:

To decrease the king's health, you can perform either of the two types of operations:

• First Type of Stab: Decrease the king's health H by 1, i.e., H = H - 1.
• Second Type of Stab: If H = H1 * H2, where H1 >= H2 > 1, decrease H to H1; here, H1 is the larger factor of H.

Input:

The initial input line contains an integer 'T', representing the number of test cases.
Each test case consists of one line containing a single integer 'N', the king's initial health.

Output:

For each test case, output a single line containing an integer representing the minimum number of stabs required.

Example:

Input:

2
10
15

Output:

4
5

Constraints:

• 1 <= T <= 10^2
• 1 <= N <= 10^3
• Time Limit: 1 sec

Note:

You are not required to print anything; just implement the given function to compute the answer.