На \textbf{i}-ому місці у послідовності чисел стоїть максимальне ціле з \textbf{i} знаків, причому цифри, які стоять поруч, різні. \InputFile Натуральне число \textbf{k} до \textbf{100000}. \OutputFile \textbf{k}-те число послідовності.