笔试题求解答，路过的大佬有没有思路呀

牛老板(牛牛)是一个土豪，他有无穷数量的纸币，但他的纸币面值很奇怪:
牛老板纸币的面值要么为6^i，要么为9^i,其中(i∈[- ∞, + ∞])且i为整数。
牛老板买了一架私人飞机售卖价格为X，牛老板希望在不找零的情况下用
尽可能少的纸币付钱，请你帮牛老板计算至少需要多少张纸币。

1输入描述
输入包含T组测试用例，第一行一个整数T
接下来T行每行一个整数X

I输出描述
输出T行，第i行为第i组测试用例的答案。