Problem Description

October 30, 2009.

After a night's journey, finally we arrived at Wuhan University in the morning to participate the International Collegiate Programming Contest (ACM-ICPC).

......

Before went to sleep, my team mate Zhang and I played a popular card-game called "Builds up Train" to have a release. Although the game is a liite stupid, but it may have a lot of fun ...


Assume there are 3 kinds of cards, and each of them has unlimited supply. If we take n cards out and arrange them in a row, we can get 3n differet rows. Now the problem is, how many different rows we can get using n cards and the number of cards of each kind is even?

Input

The first line of input is a single integer T (1 ≤ T ≤ 1000), representing the number of test cases. Then T test cases follows. Each test case is described by a single integer in a single line: n (1 ≤ n ≤ 2147483647);

Output

For each test case, output four integers in a line separated by spaces. The first integer is the number of different rows we can get using n cards when the number of cards of all kinds are even, the second integer is the number of different rows we can get using n cards when the number of cards of one kind is even and the number of cards of the other two are odd, the third integer is the number of different rows formed by n cards when the number of cards of two kinds are even and the number of cards of the other one is odd, the last number is the number of different rows formed by n cards when the number of cards of all three kinds are odd.

Output the answer mod 40007.

3
1
2
2147483647

0 0 3 0
3 6 0 0
0 0 442 13482