题目描述

这是该问题的简单版本。简单版本与困难版本的区别在于，简单版本要求在使用最少交易次数的前提下确定最小花费，而困难版本则要求在限定交易次数的情况下确定最小花费。

在狡猾的商贩卖出三只西瓜而不是一只之后，他决定进一步增加利润——也就是说，他买了更多的西瓜。现在他可以用 $3^x$ 个西瓜进行一次交易，售价为 $3^{x+1} + x \cdot 3^{x-1}$ 个硬币，其中 $x$ 是非负整数。这样的售卖被称为一次“交易”。

一位精明的买家来找他，但他时间非常紧迫。因此，他想要用最少的交易次数，恰好买到 $n$ 个西瓜。

由于买家很着急，因此他请你帮忙计算，买家在用最少交易次数买到 $n$ 个西瓜的情况下，最少需要支付多少硬币。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来每个测试用例占一行，每行包含一个整数 $n$（$1 \le n \le 10^9$），表示需要购买的西瓜数量。

输出格式

对于每个测试用例，输出一个整数，表示购买这些西瓜所需的最小花费。

说明/提示

注意，没有必要买超过所需数量的西瓜，因此我们不会考虑那些买到的西瓜数量超过所需数量的交易。

让我们来看前两种交易方式的花费：

交易 A：$1$ 个西瓜——$3$ 个硬币。

交易 B：$3$ 个西瓜——$10$ 个硬币。

在第一个样例中，唯一的方式是用一次交易 A 买 $1$ 个西瓜，因此答案是 $3$。

在第二个样例中，可以用一次交易 B 买 $3$ 个西瓜，花费 $10$ 个硬币。

在第三个样例中，可以用 $2$ 次交易 A 和 $2$ 次交易 B，总共花费 $26$ 个硬币。如果我们只进行 $3$ 次交易，可以获得 $3$、$5$、$7$ 或 $9$ 个西瓜。如果交易次数少于 $3$ 次，最多只能买到 $6$ 个西瓜，这意味着不可能用少于 $4$ 次交易买到 $8$ 个西瓜。

由 ChatGPT 4.1 翻译

样例

7
1
3
8
2
10
20
260010000

3
10
26
6
36
72
2250964728