Marisa wants to build an rectangular swimming pool for Alice. To do this, Marisa can select four integral points on an infinite 2D-grid and cast magic. For example, the following picture shows three possible ways to build a swimming pool.



Marisa soon learns that there are many ways to build the pool since four sides of the pool can be non-parallel to coordinate axis. Here two ways are considered different if and only if the pool in one way can't be translated (moved without rotation and flipping) to the pool in the other way. Now Marisa becomes curious about the total numbers of complete squares inside the pool for all possible ways. As the result can be very large, you should print it modulo .

In the first line, there is one integer  (), denoting the number of test cases.

For each test case, there is one line containing two numbers  and  (), denotes the size of swimming pool.

It is guaranteed that there are at most 10 cases that .

For each test case, print one number, denoting the total number of complete  squares inside the pool for all possible ways (modulo ).

5
5 5
2 3
5 10
2197525579 1145141
91 65

51
12
228
438744975
34722

As shown in the picture, there are exactly three different ways to build the pool. The corresponding numbers of complete  squares in these three ways are , , . So the total number is .