1862 - 守序数
描述

如果一个十进制正整数的任意两个相邻的数字之差均不超过 1,则称该数字为守序数。

1 是第一个守序数,给定 n 请求出第 n 个守序数。


输入

单个整数表示 n

输出

单个整数表示答案

样例

输入

13

输出

21
提示

30\% 的数据,1\leq n\leq 100

60\% 的数据,1\leq n\leq 10000

100\% 的数据,1\leq n\leq 1,000,000


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 161
通过次数 22