Cho hai số nguyên \(n\) và \(k\), nhiệm vụ của bạn là đếm số mảng \(a_1, a_2,\dots, a_n\) gồm các số nguyên dương sao cho \(\operatorname{lcm}(a_i, a_{i+1}) = k\) với mọi \(1 \le i < n\).

Đầu vào

Dòng đầu tiên chứa một số nguyên \(t\): số lượng bộ kiểm thử.

\(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(n\) và \(k\): độ dài của mảng và giá trị LCM.

Đầu ra

In ra \(t\) số nguyên: đáp án cho từng bộ kiểm thử modulo \(10^9 + 7\).

Constraints

• \(1 \le t \le 1000\)

• \(2 \le n \le 10^9\)

• \(1 \le k \le 10^9\)

Example

3
3 4
4 6
1337 42

11
64
602746233

Explanation

Các mảng của bộ kiểm thử đầu tiên là \([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]\) và \([4, 4, 4]\).