CSL likes playing tricks very much. The unlucky TL always becomes the target of CSL's tricks.

Today CSL came to trick TL again. He saw that TL has a very very large checkerboard and many glass balls. So he have an idea. He said to TL:

"What a big chessboard you have... How about play a game with me ? I will give you and ,and you can choose an arbitrarily large square area on the chessboard (assuming you choose a square area) and place a number of glass balls on each of the squares (each square should place not less than glass balls). Your placement needs to be satisfied:

If we choose squares of different rows and columns, then no matter how we choose, the total number of glass balls in this squares should always be the same, and should not greater then .

You just need to tell me how many ways you have to satisfy this. If you can't tell me, the chessboard and glass balls will all belong to me ！

TL doesn't want to give the chessboard and glass ball to CSL, but he knows that the clever CSL has already worked out the answer in his mind. Can you help him solve this problem?

The first line of the input is a single integer  indicating the number of test cases.

Each of the following  lines contains 2 integers  and  (meaning as description)

 , 

For each test case, output the answer in a single line. because the answer may be very big, so just print the result after mod 

5
1 1
2 1
3 1
4 1
5 1

1
3
9
26
73