有一天，小明给佳佳出了一道题，
给出一个正整数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的答案。
2
7
104
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