Trong một nghiên cứu về tương tác protein, Thanh đang mô phỏng các đại phân tử như những thành phần dao động có tần số riêng. Có ~n~ loại phân tử khác nhau, được đánh số từ ~1~ đến ~n~. Phân tử thứ ~i~ có tần số dao động tự nhiên là ~i~ Hz.

Thanh muốn chọn một số phân tử để tạo thành một phức hợp protein. Với một nhóm phân tử, tần số cộng hưởng của phức hợp được xác định bằng bội chung nhỏ nhất (BCNN) của các tần số trong nhóm. Phức hợp đó được xem là ổn định nếu tần số cộng hưởng này là một bội số của tần số nền ~k~.

Trong mô hình này, tần số nền ~k~ được biểu diễn thông qua các đơn vị cấu trúc chuẩn hóa, vì vậy mọi thừa số nguyên tố của ~k~ đều không vượt quá ~10^6~.

Nhiệm vụ của bạn là đếm số tập con không rỗng của ~1, 2, \dots, n~ sao cho phức hợp tạo thành là ổn định.

Input

• Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 100)~ là số bộ test.

• Mỗi bộ test gồm một dòng chứa hai số nguyên ~n~ và ~k~ ~(1 \le n, k \le 10^{18})~.

Dữ liệu đảm bảo ~k~ không chia hết cho bất kỳ số nguyên tố nào lớn hơn ~10^6~.

Output

Với mỗi bộ test, in ra số lượng tập con thỏa mãn yêu cầu, lấy modulo ~10^9 + 7~.

Scoring

Sample Input 1

4
4 4
6 12
18 36
10 999983

Sample Output 1

8
24
184320
0