Hôm nay nhân ngày đẹp trời, \(Kaninho\) quyết định lên mạng để học về những bài toán IQ, vô tình anh ta đọc được bài toán như sau :

Gọi \(A\) là tập hợp tất cả các số nguyên dương không lớn hơn \(n\). \(Henry\) muốn chọn một vài số từ tập đó và chúng thoả mãn \(2\) điều kiện sau:

• Số lượng các số được chọn ít nhất là \(1\) và nhiều nhất là \(k\)

• Không tồn tại số chính phương \(f(f\ne 1)\) nào thoả mãn \(f\) là ước của tích các số được chọn.

Yêu cầu: Hãy đếm xem \(Henry\) có bao nhiêu cách chọn các số như vậy.

Vì chưa có kinh nghiệm nhiều trong những bài toán như vậy, nên \(Kaninho\) quyết định lên đây để nhờ các bạn giúp đỡ. Là một lập trình viên tài năng, hãy giúp anh ấy một tay nhé !

Input

• Dòng thứ nhất chứa số \(t\) (1 \(\le\) \(t\) \(\le\) 5) - thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(n\), \(k\) (1 \(\le\) \(n\), \(k\) \(\le\) 500)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm sau khi đã mod \(10^9+7\).

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n,k\le 20\).

• Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

2
2 2
3 2

3
6