KSET

Cho hai số nguyên dương \(n\), \(k\), đếm số tập \(S\) thỏa mãn:

• \(S\) chỉ chứa các số nguyên dương là ước của \(n!\).

• \(|S| = k\);

• Gọi \(P\) là tích các số thuộc \(S\). Khi đó tất cả các ước nguyên tố của \(n!\) đều là ước của \(P\).

• Hai phần tử khác nhau \(x, y\) bất kỳ của \(S\) đều thỏa mãn \(N(x) \cdot N(y) = N(x \cdot y)\). Ở đây \(N(m)\) là số ước nguyên dương của \(m\).

Hai tập được coi là khác nhau nếu tồn tại phần tử có ở tập này nhưng không có ở tập kia.

Input

Dòng đầu chứa số lượng testcase \(T\);

\(T\) dòng tiếp theo, mỗi dòng chứa hai số \(n, k\).

Output

Ghi ra \(T\) dòng là kết quả cho \(T\) testcase sau khi chia lấy dư cho \(10^9 + 7\).

Example

2
6 3
8 3

32
182

Scoring

Trong tất cả các test \(1 \leq T, n, k \leq 10^6\); Tổng \(k\) trong tất cả các test không vượt quá \(10^6\).