题目描述

数字 9 意味无私、大爱、人道主义。9 会让我们超越个人得失带来的喜怒哀乐，将我们的眼界变得更加宏观，不再拘泥于个人名利的纠缠，将人生更大的快乐建立在帮助他人的过程上。
9 这个数字很特别，9 加任何数字都会还原。例如，9 乘以任何数还是 9；3+9=12，1+2还是等于 3；3×9=27，2+7 还是等于 9。9 代表着结束、最高以及生命的轮回，将数字 1~8依次加在一起，1+2+3+4+5+6+7+8=36，而 3+6 的答案还是 9。
从古到今，人们都承认九是最大的数字。天地间的数字“始于一，终于九”，“至十则又为一”。“十”只不过是上位的“一”，而“九”才是 0~9 这个数码中的老大哥。
在小 H 眼里，只要数字中含有 9 或者 9 的倍数，他就认为是大爱数，他在纸上写下了所有大于 0 的所有大爱数（好像不太科学，大爱数有无穷多个），但他想考考你从小到大第 k 个大爱数是多少？

输入格式

一行一个整数 k,表示小 H 想知道第 k 个大爱数是多少。

输出格式

一行一个整数，第 k 个大爱数。

样例数据

input

3

output

19

数据规模及约定】

10%的数据 1<=k<=10；
30%的数据 1<=k<=100；
50%的数据 1<=k<=10000；
100%的数据 1<=k<=1000000；