In how many ways can you tile a 2 * n rectangle with triominoes? A triomino is a geometric shape made from three squares joined along complete edges. There are only two possible triominoes:

For example, you can tile a 2 * 3 rectangle only in 3 different ways. As the answer can be quite big, you just need to find the number of ways modulo 10⁶.

Constraints : Number of test cases {t} {(1≤t≤100)}. Each of the following

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

Output : Answer modulo 10⁶.