【问题描述】
假如长江沿岸有n个城市，每个城市依次标号（上游到下游次序编）为1，2，3…, n-3, n-2, n-1, n。alg想从长江上游出发，游玩这些城市。其中alg的旅游路线选取原则为：
1.至少要游玩一个城市。
2.不会游玩相邻的两个城市。即相邻的两个城市不会出现在algoo的旅游路线中。例如：当游玩过城市n-k后，就不会考虑在城市n-k+1停下。
现在你的任务是：如果有n个城市，帮助algoo计算有多少种路线可以选择。
【要求】
【数据输入】多组测试数据。每组测试数据一行，为一个数n（1<=n<=100），表示城市的个数。
【数据输出】对每组测试数据，输出algoo总共有多少种路线选择。
【样例输入】
3
4
5
【样例输出】
4
7
12
Hint

学了一学期了！教材学完了！