Waylon Tritangle is a kind of pattern which is widely used everywhere. In a Waylon Tritangle, the  floor from top has  same blocks adjacently, and all floors' blocks are centered. For example, the following picture shows a 5-floored Waylon Tritangle.

Today, our old friend Waylon build such a -floored Waylon Tritangle Wall in City University of Hong Kong(Dongguan), after that, Yuangq takes millions of same green cards sized as exactly  blocks to cover the wall. Since green cards will look terrible onced been torn apart, he hopes that no green cards should be tear apart, so all green cards must cover exactly  blocks.

Since Yuangq is extraordinarily passionate on Math, he also expects to figure out how many different results of colored Waylon Tritangle Wall can he colors into. So, your task is to calculate that for him!

输入描述:

The first line contains a single integer  () — the number of test cases. Then  test cases follow.

Each test case contains a single integer  () — the height of Waylon Tritangle Wall.

输出描述:

For each test case, output how many different results of Waylon Tritangle Wall can Yuangq colors into in a single line. Since the result might be too huge, please output the answer after taking module to .

4
1
2
3
32749

1
2
6
771456293

As for test case , the first possible result is to do nothing:
The second possible result is to cover the  floor:

So, there are totally  different results of Waylon Tritangle Wall can Yuangq colors into.