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.\)