该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在海贼王的世界里，大雄是个闻名遐迩的糖果海贼。一天，他找到了一张古老的藏宝图，上面画着一个神秘的宝藏岛，岛上有 $n$ 个五彩缤纷的糖果。但这张藏宝图上有个特别的规则：每天只能吃1个、3个或4个糖果。
大雄咧嘴一笑，拿出他的魔法算盘：“这可是个甜蜜的任务！”他开始计算：“每天吃1个糖果，就像每天发现一颗闪亮的星星，$n$ 天就能慢慢享受完。”
“如果每天吃3个，”大雄眨了眨眼，“那就好像是找到了一个宝藏，三倍的快乐，但时间缩短了。”
“每天吃4个，”他跳起来，“那就像是找到了一个宝箱，四倍的甜蜜，但要记得，糖果有限哦！”
小海贼们围了上来，眼睛里闪烁着好奇和期待。大雄神秘地说：“这就像是我们的糖果岛冒险，每种吃法都是一种新的旅程。至于总共有多少种吃法嘛，这可是我们的秘密，嘿嘿。”

想了一会，小海贼们发现这题好像有些困难，大雄看着小海贼们纯真的眼神，只好无奈的加了一些提示：

• 吃1个糖果，我们可以第1天吃1个，只有 1 种吃法。
• 吃2个糖果，我们可以第1，2天都吃1个，有 1 种吃法。
• 吃3个糖果，我们可以前3天都吃1个，也可以第1天直接吃 3 个，有 2 种吃法
• 吃4个糖果，我们可以前四天都吃 1个； 也可以第一天吃1个，第2天吃3个；也可以第1天吃3个，第2天吃1个；也可以第一天直接吃4个，有4种吃法。
• 吃5个糖果，我们可以在吃 1 个糖果的吃法基础上，再一口气吃4个得到（多加1天，这1天吃4个糖果），也可以在吃2个糖果的基础上，一口气吃3个得到（多加1天，这1天吃3个糖果），也可以在吃4个糖果的基础上，一口气吃1个得到（多加1天，这1天吃1个糖果），所以答案是： 1 + 1 + 4 = 6 种吃法。

……

输入格式

输入第一行为 T，表示有 T 组数据($ 1\le T \le 10$)。

接下来 $T$ 行， 每行一个整数 $n$ ($1 \le n \le 200$) ，表示糖果的总数。

输出格式

对于每一组数组，输出吃掉对应 $n$ 个糖果的吃法（顺序不同也属于不同的吃法，比如第一天吃1个，第二天吃3个 和 第一天吃3个，第二天吃1个，属于不同的吃法）。

结果可能很大，输出该结果 $\%$ $37373$ 后的答案！！！

样例

2
1
3

1
2

数据范围

• 对于 $60\%$ 的数据，$1\le n \le 50$
• 对于 $100\%$ 的数据，$1\le n \le 200$