题目描述

有一天， 小明给佳佳出了一道题，给出一个正整数 n， 佳佳可以进行如下三种操作：
1、 使 n 减去 1
2、 如果 n 是 2 的倍数，使 n 除以 2
3、 如果 n 是 3 的倍数，使 n 除以 3
问佳佳最少可以通过几步操作，将 n 变为 0。
为了考验佳佳的知识水平，小明给出了 T 个数字 n_1,n_2,…,n_T，让佳佳对每个数字都给出答案。然而佳佳一心只想着晚上吃啥，想让聪明的你来帮助他解决这个问题，并答应解决后请你吃饭，于是你义不容辞地接下了这个任务。

输入格式

第一行一个正整数 T，表示总共有 T 个数字；
接下来 T 行，每行一个正整数 n_i

输出格式

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

样例数据

input

2 
7
10

output

4
4

样例 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