Everyone likes short and sweet problem statements and so here is one.

Given $N$ and $M$, you need to find $\sum _{i=1} ^M N \ mod \ i^2$. Since the answer could be large, find it modulo $10^9+7$.

Input

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.

The first and only line of each test case contains two space-separated integers $N$ and $M$.

Output

For each test case, print a single line containing one integer denoting the answer to the problem.

Constraints

$1\le T \le50$

Subtask 1 (10 points): $1\le N \le10^6, 1\le M \le10^{6}$

Subtask 2 (10 points): $1\le N \le10^{12}, 1\le M \le10^{18}$

Subtask 3 (80 points): $1\le N \le10^{18}, 1\le M \le10^{18}$

Problem Author: Ankit Kumar Singh