Given two integers n and k, your task is to count the number of arrays a_1, a_2,\dots, a_n of positive integers where \operatorname{lcm}(a_i, a_{i+1}) = k for all 1 \le i < n.

Input

The first line has an integer t: the number of test cases.

The next t lines have two integers n and k: the length of the array and the value of lcm.

Output

Print t integers: the answer to each test case modulo 10^9 + 7.

Constraints

• 1 \le t \le 1000
• 2 \le n \le 10^9
• 1 \le k \le 10^9

Example

Input:

3
3 4
4 6
1337 42

Output:

11
64
602746233

Explanation: The arrays for the first test case are [1, 4, 1], [1, 4, 2], [1, 4, 4], [2, 4, 1], [2, 4, 2], [2, 4, 4], [4, 1, 4], [4, 2, 4], [4, 4, 1], [4, 4, 2] and [4, 4, 4].