题意：一个栈中只能放入U和L，问存在连续3个以上U(危险组合)的个数为几个
分析：这个题的解法有多种。
解法1： 用总组合数-安全组合=危险组合。d[i]表示第i个位置以L结束的序列，所以就有d[i] = d[i - 1] + d[i - 2] + d[i - 3]。
解法2：设答案为f(n)。既然有3个U放在一起，可以根据这3个U的位置分类——对，根据前面的
经验，要根据“最左边的3个U”的位置分类。假定是i、i+1和i+2这3个盒子，则前i-1个盒子不
能有3个U放在一起的情况。设n个盒子“没有3个U放在一起”的方案数为g(n)=2 n -f(n)，则前i-1
个盒子的方案有g(i-1)种。后面的n-i-2个盒子可以随便选择，有2 n-i-2 种。根据乘法原理和加
法原理， 。
遗憾的是，这个推理是有瑕疵的。即使前i-1个盒子内部不出现3个U，仍然可能和i、i+1
和i+2组成3个U。正确的方法是强制让第i-1个盒子（如果存在）放L，则前i-2个盒子内部不
能出现连续的3个U。因此 ，边界
是f(0)=f(1)=f(2)=0。g(0)=1，g(1)=2，g(2)=4。注意上式中的2 n-3 对应于i=1的情况。

代码如下：

//
//Created by BLUEBUFF 2016/1/12
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
//#include <bits/stdc++.h>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 100010;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
const double PI = acos(-1);
//head

LL f[32], g[32];
void pre_deal(){
    f[0] = f[1] = f[2] = 0;
    g[0] = 1; g[1] = 2; g[2] = 4;
    for(int n = 3; n <= 30; n++){
        f[n] = 1LL<< (n - 3);
        for(int i = 2; i <= n - 2; i++){
            f[n] += g[i - 2] * (1LL<<(n - i -2));
        }
        g[n] = (1LL<<n) - f[n];
    }
}
int main()
{
    pre_deal();
    int n;
    while(scanf("%d", &n) != EOF && n){
        cout << f[n] << endl;
    }
    return 0;
}