简单版和困难版之间的唯一区别是 $$$n$$$ 的最大值。
给你一个正整数$$$n$$$。您确实喜欢好数字,因此您想找到大于或等于 $$$n$$$ 的最小好数字。
如果正整数可以表示为 $$$3$$$ 的不同幂的总和(即不允许 $$$3$$$ 的幂重复),则该正整数被称为好整数。
例如:
- $$$30$$$ 是一个好数字:$$$30 = 3^3 + 3^1$$$,
- $$$1$$$ 是一个好数字:$$$1 = 3^0$$$,
- $$$12$$$ 是一个好数字:$$$12 = 3^2 + 3^1$$$,
- 但 $$$2$$$ 不是一个好数字:你不能将它表示为 $$$3$$$ 的不同幂的总和 ($$$2 = 3^0 + 3^0$$$),
- $$$19$$$ 不是一个好数字:您不能将其表示为 $$$3$$$ 的不同幂的总和(例如,表示 $$$19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$$$ 无效),
- $$$20$$$ 也不是一个好数字:您不能将其表示为 $$$3$$$ 的不同幂的总和(例如,表示 $$$20 = 3^2 + 3^2 + 3^0 + 3^0$$$ 无效)。
请注意,$$$19$$$ 和 $$$20$$$ 还存在其他表示形式,作为 $$$3$$$ 的幂之和,但它们都不包含 $$$3$$$ 的不同幂。
对于给定的正整数 $$$n$$$ 找到最小的 $$$m$$$ ($$$n \le m$$$) 使得 $$$m$$$ 是一个好数。
您必须回答 $$$q$$$ 独立查询。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500$$$) — 查询数。然后是 $$$q$$$ 查询。
查询中唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{18}$$$)。
输出
对于每个查询,打印最小整数 $$$m$$$ (其中 $$$n \le m$$$),使得 $$$m$$$ 是一个好的数字。
示例
输入 #1
8 1 2 6 13 14 3620 10000 1000000000000000000
输出 #1
1 3 9 13 27 6561 19683 1350851717672992089