Problem Statement

A string $S = S_1 S_2 \cdots S_8$ of length $8$ is called an NUPC compressed string if it satisfies both of the following conditions.

• The odd-positioned characters $S_1, S_3, S_5, S_7$ are N, U, P, C, respectively, in this order.
• The even-positioned characters $S_2, S_4, S_6, S_8$ are each 1 or 2.

As the name suggests, an NUPC compressed string $S$ is a compressed form of some string. The original string $T$ before compression is obtained by decompressing $S$ with the following procedure.

1. Let $T$ be a string of length $0$.
2. For $i = 1, 2, \dots, 8$ in order, perform the following operation.
   • If $i$ is odd, append $S_i$ to the end of $T$.
   • If $i$ is even,
     • If $S_i$ is 1, do nothing.
     • If $S_i$ is 2, replace $T$ with "the string obtained by concatenating $T$ and $T$".

There are $16$ NUPC compressed strings in total. Given an integer $1 \leq K \leq 16$, output the $K$-th smallest string in lexicographical order among all strings obtained by decompressing NUPC compressed strings.

Input

The input is given from standard input in the following format.

$K$

Output

Output the answer to standard output on a single line, followed by a newline.

Constraints

The input satisfies the following constraints.

• $K$ is an integer satisfying $1 \leq K \leq 16$.

Sample

1

NNUNNUPC

5

NNUPC

13

NUPC