Shiva and Anshul play a game to take a break from programming. Anshul has won W coins in the previous programming contests.So, he puts N of those coins into a stack. Shiva starts first by removing s(0<s<N) coins initially and on alternate turns, each player removes some p number of coins such that p is a divisor of the number of coins removed on previous turn by the other player. The player who can not make a move loses the game. Help Anshul find the largest stack of coins N he should choose from these W coins so that he can certainly win the game.

After losing the previous game, Shiva gets furious and challenges Anshul for another game.

He gives him a M*M board containing M^2 unit squares in which some are colored white and others are colored black. He then asks him to select three squares from the board (A,B,C) such that A,B are in the same row and B,C are in same column. He also puts a condition that A and C should be white and B should be black. The maximum number of ways to select such triplets are Q(for any permutation of white and black).

Print Q*N mod 1000000007.

INPUT:

First line contains a single integer T denoting the number of test cases. T lines follow, each containing two integers W and M.

OUTPUT:

Output the answer for each test case in seperate lines.

CONSTRAINTS:

T <=100

1<=W<=1000000

1<=M<=10000