You and your friends have recently gotten into a new multiplayer online battle arena game called Defense of the Eternal Runes or DotER for short. You're all in a match, and you're facing off against the opponent team, trying to take down the enemy's heavily fortified Eternal Rune.

You're playing a wizard with a very special set of damage spells. Given an opponent's HP, the wizard can either deal ~1~ damage, halve their HP if it's divisible by two, or reduce their HP to a third if it's divisible by three. Your character gains a special buff if you're able to apply these spells, such that you use the minimum number of spells possible to get the opponent's health down to ~1~ HP.

Getting this buff would help your team immensely, so you decide to create a program to calculate the minimum number of spells needed to get an opponent's HP of ~p~ down to ~1~.

Input

The first line of input is the number of test cases ~t~ ~(1 \leq t \leq 100)~.

For each test case, each line consists of a single integer ~p~ ~(1 \leq p \leq 10^5)~, the HP of your opponent.

Output

For each test case, output a single integer, the minimum number of spells needed to get an opponent's HP to ~1~.

Example

Input 1

5
1
2
3
4
5

Output 1

0
1
1
2
3

For each HP value:

• ~1~ HP requires no further spells, so we output ~0~.
• ~2~ HP means we can either halve the HP or deal ~1~ damage to get to ~1~ HP. Therefore, we output ~1~.
• ~3~ HP means we can reduce HP to a third (i.e., dividing the HP by three) to get to ~1~ HP. Therefore, we output ~1~.
• ~4~ HP means we can halve the HP, then either halve again or deal ~1~ HP of damage. Therefore, we use a minimum of ~2~ spells.
• ~5~ HP means we first deal ~1~ HP of damage, then we can halve twice to get to ~1~ HP. Therefore, we use a minimum of ~3~ spells.