Description

有一天，小明给佳佳出了一道题，

给出一个正整数n，佳佳可以进行如下三种操作：

1、使n减去1

2、如果n是2的倍数，使n除以2

3、如果n是3的倍数，使n除以3

问佳佳最少可以通过几步操作，将n变为0。

为了考验佳佳的知识水平，小明给出了T个数字n_1,n_2,…,n_T，让佳佳对每个数字都给出答案。然而佳佳一心只想着晚上吃啥，想让聪明的你来帮助他解决这个问题，并答应解决后请你吃饭，于是你义不容辞地接下了这个任务。

Input Format

第一行一个正整数 T，表示总共有T个数字；

接下来T行，每行一个正整数n_i

Output Format

共T行，每行一个数字，第i行为对于n_i的答案。

2
7
10

4
4

Hint

【样例1解释】

7->6->2->1->0

10->9->3->1->0

【数据范围】

对于40%的数据，T≤10，n_i≤30

对于70%的数据，T≤20，n_i≤1000

对于100%的数据，T≤20，n_i≤1000000

Source