Finding the nth Self-Number

In 1949, Indian mathematician D. R. Daprekar introduced a fascinating class of numbers known as Self-Numbers. For any positive integer \( n \), define the function \( d(n) \) as:

\[ d(n) = n + \sum_{\text{digit } x \in n} x \]

For example, \( d(75) = 75 + 7 + 5 = 87 \). Starting from any positive integer \( n \), one can form an increasing sequence:

\( n,\; d(n),\; d(d(n)),\; d(d(d(n))),\; \ldots \)

In this sequence, if \( m \) immediately precedes \( d(m) \), we say that \( m \) is a generator of \( d(m) \). Some numbers have more than one generator (for instance, both 91 and 100 are generators of 101). A number with no generators is called a Self-Number. The first 13 Self-Numbers are:

\( a_1=1,\; a_2=3,\; a_3=5,\; a_4=7,\; a_5=9,\; a_6=20,\; a_7=31,\; a_8=42,\; a_9=53,\; a_{10}=64,\; a_{11}=75,\; a_{12}=86,\; a_{13}=97 \).

Your task is to compute the nth Self-Number \( a_n \) given an input index \( n \) (1-indexed).

inputFormat

The input consists of a single integer \( n \) (1-indexed), which represents the index of the Self-Number you are to find.

outputFormat

Output a single integer: the \( n \)th Self-Number \( a_n \).

sample

1

1