Description

在一个ACM交流群中，讨论着一个问题：秃头，这时，一个人提出了这样一个问题：秃头的英文是“bald”，给你一个长度为n的字符串（字符串由‘b’，‘a’，‘l’，‘d’三个字母组成），问有多少种组成方式？（其中’b‘不能连接‘b’和‘d’，‘d’也是同理，因为他们看起来太容易把人绕晕）你知道该如何解答吗？

Format

Input

输入一个整数T（0<T<30），接下来输入T组数据，每组数据有一个整数n（0<n<30）。

Output

对于每组数据，输出有多少组成方式，每组输出占一行。

Samples

2
1
2

4
10

Hint