ねえ　もしも全て投げ捨てられたら　/　Hey, if I could throw everything away,

笑って生きることが楽になるの　/　would it become easier to live with a smile?

Given two positive integers $n$ and $k$.

Define $\displaystyle f(x)=\sum_{i=1}^x \gcd(i,i\oplus x)^k$. Calculate $\displaystyle \sum_{i=1}^n f(i)$, where $\gcd(a,b)$ denotes the greatest common divisor of $a$ and $b$, and $\oplus$ denotes the bitwise XOR operation (the ^ operator in C++).

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

Input

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

Each test case consists of a single line containing two positive integers $n$ and $k$.

Output

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

Examples

Input 1

5
3 2
10 1
261 261
2333 2333
124218 998244353

Output 1

17
134
28873779
470507314
428587718

Note 1

For the first test case:

$f(1)=\gcd(1,0)^2=1$.

$f(2)=\gcd(1,3)^2+\gcd(2,0)^2=5$.

$f(3)=\gcd(1,2)^2+\gcd(2,1)^2+\gcd(3,0)^2=11$.

$f(1)+f(2)+f(3)=17$.

Constraints

For all test cases, $1\le T\le 1000$, $1\le n\le 2\times 10^5$, $\sum n\le 2\times 10^5$, $1\le k\le 10^9$.

This problem uses bundled testing.

Let $\sum n$ denote the sum of $n$ in a single test case.

• Subtask 1 (10 points): $\sum n\le 2000$.
• Subtask 2 (12 points): $\sum n\le 10^4$.
• Subtask 3 (15 points): $k=1$.
• Subtask 4 (45 points): $\sum n\le 10^5$.
• Subtask 5 (18 points): No additional constraints.