Integer sequences
are very interesting mathematical objects. Let us examine a sequence generated
with the use of two operations: doubling and “digit sorting”. The latter operation
consists in ascending-order sort of the individual digits in the decimal
representation of the argument. For example, “digit sorting” of number 5726 gives
2567.
The first member
of the considered sequence is 1. To generate a member of the sequence from the
previous member, double the previous one and apply “digit sorting” to the result.
The first 15 members of the sequence are as follows:
1, 2, 4, 8, 16, 23, 46, 29,
58, 116, 223, 446, 289, 578, 1156,
…
Write a program to determine the value of
the n-th member of
this sequence.
Limitations
1 <= n <= 2 147 483 647.
Input
The first line
contains an integer n, the number of sequence member to be calculated.
Output
The output file
should contain a single integer k, the value of the n-th member of the sequence.
Example
