Números Invisíveis

#171

Made by: Crazynds

1000MB

Considere a sequência de todos os inteiros positivos em ordem crescente: 1, 2, 3, … Alguns desses números contêm o dígito 0 na sua escrita decimal — por exemplo, 10, 20, 100, 305. Chamamos de invisível todo número que não possui o dígito 0 em nenhuma posição.

A sequência dos invisíveis é: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, …, 19, 21, …, 99, 111, …

Note que após o 9 vem direto o 11 — o 10 é "pulado" por conter um zero. Da mesma forma, 20, 30, …, 100, 101, 110, … são todos pulados.

Problema

Os números invisíveis podem ser indexados: o 1º é 1, o 2º é 2, …, o 9º é 9, o 10º é 11, e assim por diante. Dado N, encontre o N-ésimo número invisível.

Input

Um único inteiro N $(1 \le N \le 2^{63})$.

Output

Um único inteiro: o N-ésimo número invisível.

Input Example

Output Example