When you look at photographs of watches and clocks, you'll find that they almost always show the time 10:10. There are lots of theories and even urban legends about this. For example, when showing 10:10, the hands look like a smile, and so you are more inclined to buy the watch or clock :D (a form of subliminal advertising).

Now, you are given and . You are to find the number of sequences such that:

• is a number of the form for some ,
• If , then is divisible by , and is divisible by , and
• are squarefree.

Since the number can be very large, only give the number modulo .

Input Format
The first line of input contains a single integer , which is the number of test cases. The following lines contain the test cases.

Each test case consists of one line containing two integers, and .

Constraints

Output Format
For each test case, output a single line containing the answer.

Sample Input

2
2 3
3 3

Sample Output

3
62

Explanation
For the first test case, the possible sequences are:
,
,