We consider an array consisting of positive integersa1,a2,…,an of length n is good if and only if for each ai+1 is divisible by ai. Please note that we consider all the arrays with length 1 are good.
Given two integers n and mm, please count the number of good arrays whose length is no greater than n and whose largest element is no greater than mm. Since the answer may be large, you just need to output the answer modulo 109+7.
The first line of the input contains a single integer T (1≤T≤103), denoting the number of test cases.
Each of the next T lines contains two integers n,m (1≤n,m≤109), denoting a test case.
It's guaranteed that the number of test cases satisfying max(n,m)>103 will not exceed 50, the number of test cases satisfying max(n,m)>106 will not exceed 10, and the number of test cases satisfying max(n,m)>108 will not exceed 1.
5
2 4
3 5
10 12
24 17
114514 191981012
31
3915
190204
13530870