/*

    很容易我们可以手推出n = 1， 2， 3时的情况，我们假设前n - 1

    列已经放好，方法有dp[n - 1]种，第n列很显然有1种方法，那我

    再假设前n - 2列已经放好，方法有dp[n - 2]种，此时我们知道

    第n - 1和第n列肯定是横着放的，如果他们竖着放就和前n - 1列

    放好的情况相同，所以我们可以推出方程dp[n] = dp[n - 1] + dp[n - 2];

*/

#include <cstdio>

using namespace std;

typedef long long int ll;

const int maxn =  + ;

int n;

ll dp[maxn];

int main() {

    dp[] = ;

    dp[] = ;

    dp[] = ;

    for(int i = ; i <= maxn; i ++) {

        dp[i] = dp[i - ] + dp[i - ];

    }

    while(~scanf("%d", &n)) {

        printf("%lld\n", dp[n]);

    }

    return ;

}

/*

    解题思路：还是一如既往的递推...这个题和涂格子的那个题目很像

    很容易我们可以手推出n = 1， 2， 3的情况，对于第n个格子，我

    们假设前n - 1个格子已经涂好了，那么我们知道如果第n - 1个格子

    是O，那么我们第n个格子有两种涂法，如果不是O，我们第n个格子有

    三种涂法，对于第n - 1个格子，我们可以看第n - 2个格子，如果

    第n - 2个格子

*/

#include <cstdio>

using namespace std;

typedef long long int ll;

const int maxn =  + ;

int n;

ll dp[maxn];

int main() {

    dp[] = ;

    dp[] = ;

    dp[] = ;

    for(int i = ; i <= maxn; i ++) {

        dp[i] =  * (dp[i - ] + dp[i - ]);

    }

    while(~scanf("%d", &n)) {

        printf("%lld\n", dp[n]);

    }

    return ;

}

/*

    同样是递推，手推出n = 2， 3时所有未中奖的情况，我们先把

    他们抽奖假设为放东西，那么第n个参与者放东西时它可以放到

    任意一个前面的位置即n - 1种方法，我们假设为k为n放置的坐

    标，那么我们还需要将第k个放到其它位置，我们知道当第k个放

    到第n个位置时，其它n - 2个有dp[n - 2]种方法，当第k个不放

    到第n个位置时，这n - 1个有dp[n - 1]种方法放置，所以我们

    可以得出dp[n] = (n - 1) * (dp[n - 1] + dp[n - 2])。

*/

#include <cstdio>

using namespace std;

typedef long long int ll;

const int maxn =  + ;

int c, n;

ll dp[maxn];

ll mather[maxn];

int main() {

    dp[] = ;

    dp[] = ;

    mather[] = ;

    mather[] = ;

    for(int i = ; i <= maxn; i ++) {

        dp[i] = (i - ) * (dp[i - ] + dp[i - ]);

        mather[i] = mather[i - ] * i;

    }

    scanf("%d", &c);

    while(c --) {

        scanf("%d", &n);

        printf("%.2f%%\n", ((double)dp[n] * ) / mather[n]);

    }

    return ;

}

/*

    这个题可能是上一题的加强版？

    上一题是说n个人全为选中正确的百分比，这题是求n个里有m个全

    未选中的种数，高中同学应该都能想到选出m个让他们全不合格就行，

    C(n, m) * dp[m]即为方程了。

*/

#include <cstdio>

using namespace std;

typedef long long int ll;

const int maxn =  + ;

int c, n, m;

ll dp[maxn], mather[maxn];

int main() {

    dp[] = ;

    dp[] = ;

    for(int i = ; i <= maxn; i ++)

        dp[i] = (i - ) * (dp[i - ] + dp[i - ]);

    scanf("%d", &c);

    while(c --) {

        scanf("%d %d", &n, &m);

        ll p = ;

        for(int i = n - m + ; i <= n; i ++)

            p *= i;

        for(int i = ; i <= m; i ++)

            p /= i;

        printf("%lld\n", p * dp[m]);

    }

    return ;

}

/*

    这题一开始没有思路emm，去网上查了一下发现受益匪浅。

    参考直线相交，我们发现每增加一条直线就会增加n - 1个交点，

    就会增加n个平面，所以我们知道对于直线相交产生的平面个数有

    dp[n] = dp[n - 1] + n;

    对于折线呢，我们发现，每画一条折线我们总是能和之前的n - 1

    条折线多出4个交点，即总共多出4 * (n - 1) 个交点，那么就多出了

    4 * (n - 1) + 1个面，就可以得出递推方程dp[n] = dp[n - 1] + 4 * [n - 1] + 1

    对于Z型折线，画一画就可以知道每增加一条z型折线，最多能与原图的n - 1条z型折线

    共多生成9 * (n - 1) 个交点，也即可以得到递推方程为

    dp[n] = dp[n - 1] + 9 * (n - 1) + 1;

*/

#include <cstdio>

using namespace std;

typedef long long int ll;

const int maxn =  + ;

int c, n;

ll dp[maxn];

int main() {

    dp[] = ;

    for(int i = ; i <= maxn; i ++) {

        dp[i] = dp[i - ] +  * (i - ) + ;

    }

    scanf("%d" ,&c);

    while(c --) {

        scanf("%d", &n);

        printf("%lld\n", dp[n]);

    }

    return ;

}