Minimum Number of Cakes

You are given an integer total representing a total price. There is an infinite supply of cakes, where the price of each cake is a power of 3: \(3^0, 3^1, 3^2, \) and so on.

Your task is to determine the minimum number of cakes required so that the sum of their prices is exactly equal to total. This problem can be solved using a greedy algorithm by always taking the largest cake price that does not exceed the remaining total.

Mathematical Explanation: Every positive integer can be uniquely represented as a sum of distinct powers of 3 (this is essentially its base-3 representation). The goal is to use as few powers as possible, which can be achieved by selecting the largest power available at each step.

inputFormat

The first line of input contains a single integer t representing the number of test cases. Each of the next t lines contains one integer total representing the total price for that test case.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum number of cakes required to sum up to the given total price.

The result should be printed to standard output (stdout).

## sample

5
13
40
81
1
28

3
4
1
1
2

</p>