Ông chủ của Hùng không thích Hùng. Vì vậy, ông đã sa thải anh ta. Hùng quyết định vào đại học và tham gia vào ACM thay vì tìm một công việc mới. Anh ấy muốn trở thành một thành viên của đội ACM. Để tham gia, anh được giao một số nhiệm vụ lập trình và một tuần để giải quyết chúng.

Hùng không phải là một lập trình viên giàu kinh nghiệm. Thật ra anh không phải là một lập trình viên. Vì vậy, anh không thể giải quyết chúng. Đó là lý do tại sao anh ấy yêu cầu bạn giúp anh ấy với những nhiệm vụ này. Một trong những nhiệm vụ này là như sau.
Một dãy số nguyên \(b\) độ dài \(k\) : \(b[1] ,  b[2] , ...,  b[k] (1 \le b[1]  \le   b[2]  \le ...  b[k]  \le   n )\) được gọi là tốt nếu mỗi số trước là ước của số sau. Tức \(b[i]\) là ước của \(b[i+1]\) với \(i=[1..k-1]\).

Cho \(n\) và \(k\), tìm số lượng dãy tốt độ dài \(k\). Vì câu trả lời có thể khá lớn, hãy lấy nó modulo \(1000000007(10^9+7)\) .

Input

• Dòng đầu chứa \(q\) không quá \(100\)- số câu hỏi.
• Dòng đầu tiên chứa hai số nguyên cách nhau không gian \(n,k(n*k \le 10^7)\) .

Output

Xuất ra một số nguyên duy nhất-số lượng các chuỗi tốt có độ dài \(k\) modulo \(1000000007(10^9+7)\)

Example

1
3 2

5