Coco 想要制作一个由正六边形巧克力拼接成三角形形状的巧克力。为了让制作过程更有趣，她决定像下图一样，用两种巧克力拼接出一种图案。白色的是白巧克力，蓝色的是薄荷巧克力。
制作这种图案的具体方法如下：
- 最顶端的顶点处必须放置薄荷巧克力。
- 从任意一个薄荷巧克力所在的位置出发，按照以下方式可以到达的所有位置也必须放置薄荷巧克力：
- 向有相邻巧克力的任意方向移动 1 格，然后向左或向右旋转 60 度再移动 1 格。
如果像图中那样按横向顺序进行编号，求编号第 $n$ 小的薄荷巧克力的编号。
输入格式
第一行包含测试用例的数量 $T$（$1 \le T \le 10^5$）。
接下来的 $T$ 行，每行包含一个整数 $n$（$1 \le n \le 10^{16}$）。
输出格式
对于每个测试用例，在一行中输出编号第 $n$ 小的薄荷巧克力的编号。
样例
输入样例 1
6 2 7 18 281 8284 59045
输出样例 1
5 20 52 841 24850 177133