Cho dãy số nguyên gồm \(n\) phần tử \(a_1,a_2,...,a_n\) với \(a_i(1\le i\le n)\) thuộc tập hợp \(\left\{1,2,3,...,K\right\}\)

Như vậy, tức là có \(K^N\) dãy như vậy.

Yêu cầu: Tính tổng của tất cả \(gcd(a_1,a_2,...,a_n)\) của \(K^N\) dãy trên.

Ghi chú: \(gcd(x,y)\) tức là ước chung lớn nhất của hai số \(x,y\)

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 10)\) - Thể hiện số testcase

• \(t\) dòng tiếp theo,ứng với mỗi dòng, gồm \(2\) số nguyên \(N,K(2\le N\le 10^5,1\le K\le 10^5)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm mod \(10^9+7\)

Example

1
2 2

5