Find the nth Smith Number

A Smith number is a composite number whose sum of digits is equal to the sum of digits of its prime factors. In other words, for a composite number ( N ), if we let the sum of its digits be ( S(N) ) and the sum of the digits of its prime factors be ( S(F(N)) ), then ( N ) is a Smith number if ( S(N) = S(F(N)) ). Given a positive integer ( n ), your task is to compute the ( n^{th} ) Smith number. For example, the first few Smith numbers are: 4, 22, 27, 58, 85, ... Note that the first Smith number is 4.

inputFormat

The input consists of a single integer ( n ) read from standard input, which indicates that you need to find the ( n^{th} ) Smith number.

outputFormat

Output a single integer representing the ( n^{th} ) Smith number to standard output.## sample

1

4