题目描述

野豌豆是一个贪吃鬼，每天都要吃掉一个野豌豆数，野豌豆在第$k$天会吃掉第$k$小的野豌豆数。野豌豆数是一个正整数，且如果一个正整数被称为野豌豆数，当且仅当它同时满足下列两个条件：

• 写成没有前导零的十进制后，不存在相邻两位相同；
• 写成没有前导零的十进制后，不存在相邻两位和为$9$。

野豌豆的寿命极长，他想知道，他在第$k$天吃掉的野豌豆数是多少。

输入格式

输入仅包含一行一个正整数$k$。

输出格式

输出仅包含一行一个正整数，表示答案。

样例

17

19

100

132

数据范围

对于30%的数据，$1\le k\le 10^6$。

对于100%的数据，$1\le k\le 10^{17}$。

提示

1至19这19个正整数中，11和18不满足条件，所以第17个满足条件的正整数是19。