2668：铺瓷砖-3

有$$1 \times n$$的一个长方形，欲用若干$$1 \times 1，1 \times 2，1 \times 3$$的瓷砖铺满这个长方形。

下图为$$n=3$$时的长方形：

此时用$$1 \times 1、1 \times 2$$和$$1 \times 3$$的瓷砖铺满方格，共有$$4$$种铺法。

第一行是一个正整数$$T$$表示测试案例的数量。（$$1 \leq T \leq 70$$）

每组案例包含一个正整数$$n$$表示长方形的长。（$$1 \leq n \leq 70$$）

针对每组案例，输出铺法的数量。

2

1

3

1

4

题单#18（递推与记忆化搜索）