题目描述：

背景

查理・达克布朗又坐在一堂枯燥乏味的计算机科学课上：此刻，老师正在讲解经典的汉诺塔问题，这可把查理无聊得要命！

老师指着黑板（图 4）说道：“那么，问题是这样的：这里有三根塔柱：$A$、$B$ 和 $C$。有 $n$ 个圆盘。在解这个谜题的过程中，$n$ 这个数量是固定不变的。所有圆盘的大小都不相同。初始时，这些圆盘都堆叠在塔柱 $A$ 上，并且从顶部到底部圆盘的大小是逐渐增大的。这个谜题的目标是把所有圆盘从塔柱 $A$ 转移到塔柱 $C$。每次只能将一个圆盘从某根塔柱的顶部移动到另一根空的塔柱上，或者移动到另一根塔柱上顶部圆盘比它大的塔柱上。所以，你们的任务是编写一个程序，计算出将所有圆盘从塔柱 $A$ 移动到塔柱 $C$ 所需的最少移动次数。”查理说：“这太无聊了 —— 每个人都知道这可以用一个简单的递归来解决。我才拒绝编写这么简单的东西呢！”老师叹了口气：“好吧，查理，那我们来想想给你安排点别的事做：对你来说，这里有第四根塔柱 $D$。计算出使用这四根塔柱，将所有圆盘从塔柱 $A$ 移动到塔柱 $D$ 所需的最少移动次数。”查理一脸困惑地看着：“呃…… 好吧，我不知道对于四根塔柱的情况有什么最优算法……”

问题

所以，真正的问题在于解决问题并不是查理所擅长的事情。实际上，查理唯一真正擅长的事情就是 “坐在一个能完成这项任务的人旁边”。现在猜猜看 —— 没错！坐在查理旁边的人就是你，而且他已经在盯着你了。幸运的是，你知道对于 $n \leq 12$ ，下面这个算法是可行的：首先，固定塔柱 $A$ 上 $k \geq 1$ 个圆盘，然后使用四根塔柱的算法将剩下的 $n - k$ 个圆盘从塔柱 $A$ 移动到塔柱 $B$。接着，使用三根塔柱的算法将塔柱 $A$ 上剩下的k个圆盘移动到塔柱 $D$。最后，再次使用四根塔柱的算法将塔柱 $B$ 上的 $n - k$ 个圆盘移动到塔柱 $D$（这样就不会移动已经在塔柱 $D$ 上的 $k$ 个圆盘）。对所有 $k \in \{1, \ldots, n\}$ 都执行这个操作，然后找出移动次数最少的k值。所以，当 $n = 3$ 且 $k = 2$ 时，你首先要使用四根塔柱的算法将 $1$($3 - 2$）个圆盘从塔柱 $A$ 移动到塔柱 $B$（移动一次）。然后，使用三根塔柱的算法将塔柱 $A$ 上剩下的 $2$ 个圆盘移动到塔柱 $D$（移动三次）。最后一步是再次使用四根塔柱的算法将塔柱 $B$ 上的圆盘移动到塔柱 $D$（再移动一次）。因此，对于 $n = 3$ 且 $k = 2$ 的情况，总共需要移动 $5$ 次。为了确定这对于 $n = 3$ 来说确实是最佳解决方案，你需要检查 $k$ 的其他可能值 $1$ 和 $3$ 。（不过，顺便说一下，$5$次确实是最优的……）

输入：

没有输入

输出：

对于每一个$n$($1 \leq n \leq 12$），打印单独的一行，这一行包含使用四根塔柱解决 $n$ 个圆盘问题所需的最少移动次数。

输出数据1

没有输入

输出数据1

请参考输出内容。

来源：

2002 年达姆施塔特工业大学编程竞赛，德国达姆施塔特