题目描述

九连环是中国传统民间智力玩具，以金属丝制成$9$个圆环，将圆环套装在横板或各式框架上，并贯以环柄。玩时，按照一定的程序反复操作，可使$9$个圆环全部拆解下来，或全部套到炳上。

初始状态，所有环都套在炳上

最终状态，所有环都被拆解下来

初始时，九个环都在炳上，我们从左到右把九个环依次标记为$h_9,h_8,...,h_2,h_1$由于每个环互相制约，想要拆下/上环$h_n$（$n\\geq 2$），就必须满足两个条件：

1. 环$h_{n-1}$在炳上；

2. 环$h_{n-2},h_{n-3},...,h_1$全都不在炳上。

另外，环$h_1$可以随意上/下，不需要满足以上条件。

蓝蓝喜欢研究中国古代民间智慧，所以她想知道：如果初始时九个环都套在炳上，按照最优策略，环$h_k$第一次被拆解下来时，是第几步（每上或者下一个环记一步）。由于她是初学者，所以她想请你来帮她解决这个问题。

输入格式

输入只有一行，一个整数$k$，$1\\leq k \\leq 9$

输出格式

一个整数，代表按照最优策略，环$h_k$第一次被拆解下来时，是第几步。

样例

1

1

2 

1

5

6

提示

所求的是按照最优策略，环$h_k$第一次被拆解下来时的步数，当$k=5$时，我们用$1$代表环在炳上，$0$代表环不在炳上，从左到右依次是$h_9,h_8,...,h_2,h_1$，按照最优策略的拆解步骤（其中下划线标注的是$h_5$）：

初始：$1111\\underline{1}1111$

第一步：$1111\\underline{1}1110$

第二步：$1111\\underline11010$

第三步：$1111\\underline11011$

第四步：$1111\\underline11001$

第五步：$1111\\underline11000$

第六步：$1111\\underline01000$

至此，环$h_5$已经被拆解下来。