Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Sereja asks you to find out number of arrays A of size N, i.e. A_{1}, A_{2}, ..., A_{N} (1 ≤ A_{i} ≤ M), such that for each pair i, j (1 ≤ i < j ≤ N) gcd(A_{i}, A_{j}) = 1.

As the answer could be large, print it modulo 10^{9} + 7 (1000000007).

------ Input ------

First line of the input contain an integer T - number of test cases.

T tests follow. First line of each test case contain two space separated integers N, M.

------ Output ------

For each test case output required answer modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 10 $
$1 ≤ N ≤ 10^{5} $
$1 ≤ M ≤ 100 $

------ Subtasks ------

$Subtask #1: (10 points, TL = 5 secs) 1 ≤ N, M ≤ 10 $
$Subtask #2: (25 points, TL = 5 secs) 1 ≤ N ≤ 100 $
$Subtask #3: (65 points, TL = 5 secs) original$

------ Example ------

Input:
2
1 1
3 3

Output:
1
13

见题面

见题面