#1964 Virus

42  1 s   128 MB  

Description

Ajou university is attacking by hanaya1, the craziest creature on Earth.

He is using hanaya virus to occupy Ajou university`s network.

This virus has weird random rules, and destroy all network when it's number of population becomes N.

Virus starts with one. Every seconds, it can be increase two times or divides into three (below decimal points will be discarded).

You haved to find the minimum counts that virus becomes N.

Input

First line, there will be Testcase T

second line, there will be N ( 1 <= N <= 10,000 )

Output

Print the minimum seconds that virus becomes N

Sample Input

Sample Output

1
10
6

HINT

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 10