这是问题的简单版本。简单版本与困难版本的不同之处在于,它需要用最少的交易次数确定最小成本,而困难版本则需要用有限的交易次数确定最小成本。
狡猾的卖家卖掉了三个西瓜而不是一个后,他决定增加利润——也就是说,他买了更多的西瓜。现在他可以以 $$$3^{x+1} + x \cdot 3^{x-1}$$$ 的价格出售 $$$3^x$$$ 西瓜,其中 $$$x$$$ 是一个非负整数。这样的销售称为交易。
一位精明的买家来找他,但他的时间非常少。因此,他想买 $$$n$$$ 西瓜,使得 最少 可能的交易数量。
买家很着急,因此请您确定他必须向卖家支付 $$$n$$$ 西瓜的最低硬币数量,考虑到他将在 最少 可能的交易数量。
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。每个测试用例的描述如下。
每个测试用例的一行中,有一个整数 $$$n$$$ $$$(1 \le n \le 10^9)$$$ — 需要购买多少个西瓜。
输出
对于每个测试用例,输出一个整数——西瓜的最小成本。
示例
输入复制
713821020260010000
输出复制
3 10 26 6 36 72 2250964728
注意
请注意,购买超出需要的西瓜是没有意义的,因此我们不会考虑西瓜数量超出需要的交易。
让我们考虑一下前两个交易选项的成本:
交易 A:$$$1$$$ 西瓜 — $$$3$$$ 硬币。
交易 B:$$$3$$$ 西瓜 — $$$10$$$ 硬币。
在第一个示例中,购买 $$$1$$$ 西瓜的唯一方法是使用交易 A,因此答案是 $$$3$$$。
在第二个示例中,您可以使用单个交易 B 以 $$$10$$$ 硬币购买 $$$3$$$ 西瓜。
在第三个示例中,您可以进行 $$$2$$$ 交易 A 和 $$$2$$$ 交易 B,总共花费 $$$26$$$ 硬币。如果我们进行 $$$3$$$ 交易,我们可以获得 $$$3$$$、$$$5$$$、$$$7$$$ 或 $$$9$$$ 西瓜。如果我们的交易少于 $$$3$$$,我们将获得不超过 $$$6$$$ 西瓜,这意味着不可能以低于 $$$4$$$ 的交易购买 $$$8$$$ 西瓜。