1862 - 守序数
Description

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

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


Input

单个整数表示 n

Output

单个整数表示答案

Examples

Input

13

Output

21
Hint

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

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

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


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 161
通过次数 22