Lucky Numbers: Harshad in Bases 2, 8, 10, and 16

A positive integer (n) is called a Harshad number in base (b) if it is divisible by the sum of its digits when expressed in base (b). For example, (126) is a Harshad number in base 10 since (126 \bmod (1+2+6)=0). Also, (126) in base 8 is represented as (176_8) and (126 \bmod (1+7+6)=0); in base 16, (126) is (7E_{16}) (with (E) meaning 14) and since (7+14=21), we have (126 \bmod 21=0).

A number is defined as a lucky number if it is a Harshad number in all of the four bases: 2, 8, 10, and 16. The first 10 lucky numbers in their decimal forms are: 1, 2, 4, 6, 8, 40, 48, 72, 120, 126, …

Given an integer (n), your task is to determine the (n)th lucky number. In particular, if (n=2023), you should output the 2023rd lucky number (in decimal). All formulas are written in (\LaTeX) format.

inputFormat

The input consists of a single integer (n) ((1 \le n \le 10^5)), which represents the position in the sequence of lucky numbers.

outputFormat

Output a single integer: the (n)th lucky number in decimal.

sample

1

1