As you may already know, Eddy likes to walk around. Especially, he likes to walk in a number line called "Infinite line". Actually, it's exactly a line with infinite length!

Eddy is at number 0 and starts to walk around. Since Eddy is a little drunk(just finished his work, make sense), he will not walk in a fixed length. Instead, he will independently uniformly randomly walk in an integer length between 1 and K. That is, he will walk for 1 unit of length in a probability of , 2 units in , , K units in . If he currently stands on number i and walk for j unit of length, he will end up on number i+j.

Since Eddy is drunk, he will walk around infinitely. You, somehow, notice this weird thing and start wondering whether will Eddy ever step on the number N. However, you don't want to wait for such stupid thing. You would like to compute the probability that Eddy would ever step on number N.

The first line of input contains an integers T.
Following T lines each contains two space-separated integers  and .
If ,  is a number approaching infinity.

For each i, output one line containing a number representing the probability.
you should output the number module .
Suppose the probability is , the desired output will be 

3
1 0
2 1
3 -1

1
500000004
500000004