Little PandeyG is a curious student, studying in HEgwarts. Being smarter, faster and displaying more zeal for magic than any other student, one by one he managed to impress the three hidden witches of the school. They knew his secret desire to be a warrior, so each of them gave him some super power to use if he's up for a fight against one of his enemies.
- The first witch: She gave PandeyG the power to take away one unit of strength away from his enemies. - Eg \(36 - 1 = 35\).
- The second witch: Jealous of the first witch, the second one gave the kid the power to halfen the strength of his enemies. - Eg. \(\frac{36}{2} = 18\).
- The third witch: Even better, she gave him the power to reduce the strength of his enemies to one third of what it initially was. - Eg. \(\frac{36}{3} = 12\).
The witches, though, clearly told him that he'll be only able to use these powers if the strength of the opponent is an integer, otherwise not.
Since, PandeyG is one smart kid, he knew that by using all three of the powers he has got, he'll be able to defeat every enemy he's ever going to face, sometime or the other, in some number of moves.
Now, here's the twist: In spite of having all these powers, PandeyG was still losing matches against his enemies - because he was unable to use them in the optimal fashion. To defeat an opponent, you need to make sure that the enemy has only 1 unit of strength left in him.
Given the value 'k' - k being the units of the enemy of PandeyG's strength, help PandeyG figure out the minimum number of magical hits he'll be needing to defeat his opponent, using his powers.
Input Format: The first line represents the number of test cases, t. Followed by t lines - and on every line, a number n - with the strength unit of your enemy.
Output format: For every number n, print the minimum number of hits needed to defeat his enemy by making his strength equal to 1.
Constraints:
- \(1<=t<=1000.\)
- \(1<=n<=10^9.\)
In the first test case, the enemy's power is already 1, so you will no move to defeat him.
In the second case, the enemy's power can be reduced to 1 simply by using the second witch's power - reducing 2 to 1, in one step.
In the third case, the enemy's power can be reduced to 1 in one step again using the third witch's power.
In the fourth case, PandeyG can reduce the enemy's power in 2 steps, by using his second power twice.
In the fifth case, there are two ways: Way 1: Reduce 5 by 1 to make 4. Half it. \(\frac{4}{2} = 2\). Half it.\( \frac{2}{2} = 1\).
3 steps.
Way 2: Reduce 5 by 1 to make it 4. Reduce 4 by 1 to make it 3. Reduce 3 to 1, by making it one third. \(\frac{3}{3} = 1\).
3 steps.
In any case, you need to print the MINIMUM number of steps needed.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor