Description

在国际象棋的8*8方格的棋盘上如何放置8个皇后，使这8个皇后不能互相攻击，即任意两个皇后不允许处在同一横排、同一纵列，也不允许处在同一与棋盘边框呈45度角的斜线上。假设一个解用一个8位数表示，若其中第i个数字为j，则表示第i行的第j列的格子里放置一个皇后。比如15863724是一个正确的解，其代表的8皇后的位置如下图所示：

Input

输入一个正整数n。

Output

输出按照递增序列排列的解空间的第n项解。

Sample Input

2

Sample Output

16837425

HINT

Source

NBU OJ