题目描述

如果一个正整数 $X$ ，任意相邻的两个数字都不相同，则称为邻异数。

例如，$3$、$170$、$1234$ 都是邻异数；而 $11$、$6000$ 则不是。

给定正整数 $K$，请你求出从小到大第 $K$ 个邻异数。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入按以下格式从标准输入读入。

$T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$

每组数据为一行，包含一个整数 $K$。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

输入输出样例 #1

输入 #1

2
24
114514

输出 #1

26
182957

说明/提示

限制

• $1 \leq T \leq 100$
• $1 \leq K \leq 10^{12}$
• 所有输入均为整数。