Problem statement is simple. Given A and B you need to calculate S(A, B).

Here, f(n)=n, if n is square free otherwise 0. Also f(1)=1.

Input

The first line contains one integer T - denoting the number of test cases.

T lines follow each containing two integers A, B.

Output

For each testcase output the value of S(A, B) mod 1000000007 in a single line.

Constraints

• T <= 1000
• 1 <= A, B <= 1000000

Example

Input:
3
42 18
35 1
20 25
Output:
306395
630
128819