题目描述

当下列条件满足时，一个整数 XXX 被称为 Lunlun number：

• 在$X$的十进制表示中，每相邻的两位的差为 $0$ 或 $1$。

举些例子来说，$1234$，$111$，$334$ 都是 Lunlun number，而 $31415$，$119$，$13579$ 都不是。

给定一个整数 $K$ ($1 \le K \le 10^5$)，输出第 $K$ 小的 Lunlun number。

输入格式

输入一个整数 $K$

输出格式

输出一个整数代表答案

15

23

1

1

13

21

100000

3234566667

提示

数据范围

• $1\ \leq\ K\ \leq\ 10^5$

样例 1 解释

前 $15$ 个数字分别是 $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $11$, $12$, $21$, $22$, $23$