Gandalf is fighting a Balrog in abandoned dwarf city of Moria.
Unfortunately he doesn't have much time and want to end fight as soon as possible.
As Gandalf is poor in maths you have to help him in forming the strategy.
Balrog has power which is denoted by a number X. Gandalf has three types of weapon
first one can reduce the power of Balrog to half, another weapon reduces Balrog's
power to one third of the current power. The last weapon only reduces Balrog's power
by decrementing it by one.
To kill Balrog, Gandalf has to reduce his total power to zero by using minimum number of strike.

 

Input

 

The first line of input contains a integer T which denotes the number to test cases.
After which T lines follows. Every line contains an integer X which denote the initial power of Balrog.

 

Output

 

For every test case output a integer in a new line which denotes the minimum number of strikes required to kill Balrog.

 

Input Constrain:

1

Example:

Input: 2 10 19 Output: 4 5

Explanation:

In 1st test case:
First use weapon which reduce power by 1. Then use weapon which reduce power to one third twice.
Then again the weapon which reduce power by 1.
10-1=9
9/3=3
3/3=1
1-1=0