1011：覆盖问题

在一个 2^k × 2^k 的棋盘中，有一个随机位置上的方格被覆盖了，如下图：这是一个 k = 2 时的棋盘，其中第一行第三列被覆盖了。

现在你需要使用一个 2 × 2 的缺角方格（如下图）来覆盖这个棋盘，注意：缺角方格可以旋转；被覆盖过的地方不能重复覆盖；缺角方格的放置不能超过棋盘边界。请问你需要多少个缺角方格。

第一行是一个正整数 m 表示有 m 组测试数据。

每组测试数据包含一个正整数 k (1 <= k <= 30)。

针对每组数据，输出你需要的缺角方格数量，然后换行。

3

1

2

3

1

5

21

Beta Code Round#3