Counting Again?#6013
Given an integer , in how many ways you can tile a 4 \times n rectangle with 3 \times 1 tiles?
Because the answer can be large, we are interested in the remainder after answer is divided by .
First line contains the number of test cases (1 \le t \le 100). Each test case consist of a single line containing an integer (1 \le n \le 10000).
For each test case print the remainder after answer is divided by .
Example 1