You are given datasets where each dataset is in the form of two integers, and , such that:
For each dataset, find and print the following on a new line:
where is the count of divisors of . As the answer can be quite large, print the result of this value modulo .
Input Format
The first line contains an integer, , denoting the number of datasets.
Each line of the subsequent lines contains two space-separated integers describing the respective values of and for dataset .
Constraints
Output Format
For each dataset, print a single integer denoting the result of the summation above modulo on a new line.
Sample Input
3
2 0
3 0
2 4
Sample Output
18
180
588
Explanation
For the first dataset where and ,
has the following divisors: . Therefore, the result is:
Thus we print the value of on a new line.