Problem Description

As you know, AekdyCoin loves games.One day，he got a small square board such as the one in Figure 1，the length of side is A (Here A is an integer!).

Now AekdyCoin has C different color, he uses these color to paint the A * A board above. You could see a possible painted board in Figure 2.
If one board could be rotated to another board (both painted), we consider them as the same, just as you could see in the figure 3。 Now，AekdyCoin cut the A*A board into A*A small square boards whose length of side is exactly 1.Then AekdyCoin combine some squares to some new B*B squares(as many as possible)，here :
B * B * K + 1 = A * A, (K >= 0)
in the figure 5, there are two possible ways, B = 1 or B = 2
Then AekdyCoin connect the left one 1 * 1 square to other B * B square(s), as in the figure 6 But all the state you get if you rotate any B * B square(s) or rotate the figure around the left one 1 * 1 square are considered as the same. For example, all the states in Figure 7 are same. Now AekdyCoin want to know the unique state he could get if he try any possible combination .(That means he will try all possible B)

Input

The first line is an integer T indicates the number of the cases. ( T <= 1000)
Then T lines
A C
Indicate the value of A and the kind of colors AekdyCoin has. (1<=A,C<=10^9)

Output

Output a single integer indicates the remainder of the answer after divided by 1000000007

2
2 7
3 2

Case 1: 833
Case 2: 114

Author

AekdyCoin