题目描述

给你一个整数 $n$。你需要输出第 $n$ 个 “ $521$ 数字”。

这里的“ $521$ 数字”是指满足以下条件的正整数：

• 这个数在十进制表示下，仅能出现"5"、"2" 和 "1" 三个数字中的一种，其他数字不能出现，“ $521$ 数字”的大小关系和它们在十进制表示下的大小关系相同.

输入格式

第一行一个整数 $T$ ，表示输入一共有 $T$ 组。

每组第一行一个整数 $n$。

输出格式

输出 $T$ 行，一个整数，表示该组中第 $n$ 个“ $521$ 数字”。

样例

10
1
2
3
4
5
6
7
8
9
10

1
2
5
11
12
15
21
22
25
51

7
30
31
36
114
514
720
1919810

255
511
525
5515
125251
222125
5121111555252

提示

【数据范围】

• 对于 $100\%$ 的数据，$1 \le T \le 10,1 \le n \le 10^{18}$。