Description

Given two integers $n$ and $m$. You need to find the sum of $x^2\bmod(y^2-xy)$ over all pairs of integers $(x,y)$ that satisfy the following two conditions:

• $1\le x< y\le n$
• $x\oplus y=\gcd(x,y)\le m$

Here, $\oplus$ denotes the bitwise XOR operation.

Since the result can be very large, output the answer modulo $10^9+7$.

Input Format

There are multiple test cases. The first line contains a single positive integer $T$, indicating the number of test cases.

For each test case, there is a single line containing two integers, $n$ and $m$.

Output Format

For each test case, output a single line containing one integer, representing the answer modulo $10^9+7$.

3
8 3
11 3
114514 11451

7
13
184193935

Hint

For all test data, it is guaranteed that:

• $1\le T\le 3000$
• $2\le n\le 10^9$
• $1\le m\le n$
• $1\le \sum m\le 10^5$

This problem uses subtasks for grading. The description for each subtask is as follows: