問題文

長さ $8$ の文字列 $S = S_1 S_2 \cdots S_8$ が以下の2つの条件を満たすとき、 $S$ をNUPC圧縮文字列とよびます。

• 奇数番目の文字 $S_1, S_3, S_5, S_7$ は、それぞれ順に N, U, P, C である。
• 偶数番目の文字 $S_2, S_4, S_6, S_8$ は、 1 または 2 である。

NUPC圧縮文字列 $S$ は、名前のとおり、ある文字列を圧縮したものです。 以下の手順で解凍することで、圧縮前の文字列 $T$ が得られます。

1. $T$ を長さ $0$ の文字列とする。
2. $i = 1, 2, \dots, 8$ に対し、順に以下の操作を行う。
   • $i$ が奇数のとき、 $T$ の末尾に $S_i$ を加える。
   • $i$ が偶数のとき、
     • $S_i$ が 1 ならば、何もしない。
     • $S_i$ が 2 ならば、 $T$ を「 $T$ と $T$ を連結した文字列」で置き換える。

さて、NUPC圧縮文字列は全部で $16$ 種類存在します。 整数 $1 \leq K \leq 16$ が与えられるので、 NUPC圧縮文字列を解凍して得られる文字列すべて のうち、辞書順で $K$ 番目に小さいものを出力してください。

入力

入力は以下の形式で標準入力から与えられます。

$K$

出力

標準出力へ一行で出力し、最後に改行してください。

制約

入力は以下の制約を満たします。

• $K$ は $1 \leq K \leq 16$ を満たす整数である。

サンプル

1

NNUNNUPC

5

NNUPC

13

NUPC