Itou Kaiji, a smart gambler, lost all his money once again and owed Hyodo Kazutaka a huge sum of money, who is very cruel and proposes a game to bet on Kaiji's four fingers!

Hyodo has a box with nearly identical balls in it, where the -th ball has an integer number on it, which is the only difference among the balls. At the first, Kaiji will be blindfolded, which means that he cannot see anything, then Hyodo will \textbf{arbitrarily} choose two close balls(Formally, assuming that the two chosen balls are and , there is no that ), take them out of the box and put them into Kaiji's two hands. After that, Kaiji has to say ``left hand'' or ``right hand'', and Hyodo will tell him the number on the ball in the claimed hand. Finally, the most important part, Kaiji will answer the size relationship(greater than, less than, or equal to) between the told number and the number on the ball in the other hand. If Kaiji's answer is correct, he will be forgiven the debt, or he will lose his life.


Now, Kaiji needs your help, he wants to know the highest winning probability that can be guaranteed no matter what Hyodo's strategy is.


Note Kaiji will know all the numbers on balls and the whole rule before he is blindfolded.

The first line contains one integer , denoting the number of test cases.

For each test case:

Only one line contains  integer , denoting the number of balls and generate parameters of , where


It is guaranteed that  among all test cases.

For each test case:

Output one line containing one integer, denoting the winning probability modulo . 

Note that for a rational number  and an integer , if  holds, we say that  modulo  equals . In this problem, you can assume that there will be exactly one integer which equals the winning probability modulo .

2
4 1 0 1 0 2
4 1 0 1 0 4

499122177
665496236

For the first test case:

, one possible optimal strategy for Kaiji is:

Choose left hand or right hand randomly. Then:

     if the heard number is 1, guess two numbers are equal with a  probability, number on ball in the other hand is greater than number has been told with a  probability.
     if the heard number is 2, guess two numbers are equal with a  probability, number on ball in the other hand is less than number has been told with a  probability.

Under this strategy, Kaiji will have a  probability of winning, no matter how Hyodo chooses balls.

Here  and  is the only integer which equals  modulo , so the answer integer is .