rakesh loves to play number games. when He was surfing on google he found one of the game. The theme of the game is to find the shortest way that he can make the number equal to 1. He can only perform only three operations they are -1, /2, /3. As the level of game increased and he was facing difficulty to solve the large numbers, So he wanted solve this problem for him.

INPUT: first line consists of T test cases. Next T lines consists of a decimal number N.

OUTPUT For every number return the shortest way to make it to 1.

0< T < 100 0<N<10^9