Prime 的谜题

题目描述

Rick 发现了 Prime Rick 的踪迹，但当他赶到现场时，对方已经逃之夭夭，只留下了一串奇怪的序列。我们的 Rick C-137 确信 Prime Rick 留下了寻找他的线索，于是他试图破解序列中隐藏的所有信息。

序列从 $1$, $2$, $3$, $4$, $8$, $12$, $5$, $10$, $15$, … 开始。Rick 很快就猜出了它的生成方式：

1. 初始时取一个空序列；
2. 选择不在序列中的最小自然数（为了方便，记为 $x$）；
3. 将 $x$, $2 \cdot x$ 和 $3 \cdot x$ 依次写入序列的末尾；
4. 回到步骤 2 重复。

为了追踪 Prime Rick，我们需要能够快速找出序列中的第 $n$ 项。请解决这个不简单的问题！

输入格式

第一行包含一个整数 $t$ —— Rick 感兴趣的序列元素个数（$1 \le t \le 1000$）。

接下来 $t$ 行中的第 $i$ 行包含一个整数 $n_i$ —— Rick 感兴趣的第 $i$ 个元素在序列中的位置（$1 \le n \le 10^{15}$）。

输出格式

对于每个 $n_i$，输出这个神秘序列中的第 $n_i$ 个数。

示例

输入

9
1
2
3
4
5
6
7
8
9

输出

1
2
3
4
8
12
5
10
15