You are given the health of the king as an integer N. You need to find the minimum number of stabs to kill the king. The king dies if the health becomes 0.
At any point, to decrease the health of the king you can apply either of two operations (types of stab):
1. The first kind of stab decreases the king’s health h by 1 i.e h = h-1.
2. The second kind of stab decreases the king’s health to h1, where h= h1*h2 and h1 >= h2 > 1 i.e if h = h1*h2, then h can decrease to h1 where h1 is the larger factor.
1. The king’s initial health is an integer and always positive.
2. After each step, the king’s health is decreased. It can not remain the same after a stab of either type.
The first line of the input contains an integer T, denoting the number of test cases.
The first line and the only line of each test case contains an integer N, denoting the initial health of the king.
The only line of output of each test case should contain a value denoting the minimum number of stabs required to kill the king.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= N <= 10^3
Time Limit: 1sec
Sample Input 1:
Sample Output 1:
Explanation for sample input 1:
We know that, 8 = 4*2. So, we can reduce kings health from 8 to 4 after one stab of type 2.
Now since, 4 = 2*2, so after the second stab of type 2, king’s health reduces from 4 to 2.
The current health of king = 2. After the third stab of type 1, the king’s health reduces from 2 to 1.
Finally, after the fourth stab of type 1, the king’s health reduces from 1 to 0.
So, in total it takes 4 steps at minimum to kill the king.
Sample Input 2:
Sample Output 2: