At the i-th position in the sequence is the largest integer with i digits, where every pair of adjacent digits is different.
A natural number k (1 \leq k \leq 100000).
Output the k-th number in the sequence.
Example 1
