← 返回题目列表

Codeforces · 1249/C1

C1. 好数字(简易版)

中文机器翻译题面 查看原题

简单版和困难版之间的唯一区别是 $$$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^4$$$)。

输出

对于每个查询,打印最小整数 $$$m$$$ (其中 $$$n \le m$$$),使得 $$$m$$$ 是一个好的数字。

示例

输入 #1

7
1
2
6
13
14
3620
10000

输出 #1

1
3
9
13
27
6561
19683