Panda is preparing for a family get together. She decided to enjoy some traditions of her family. To impress everyone she decides to show her skills in the meeting.

A traditional array is an array in which all the adjacent elements are happy. Adjacent elements are happy if and only if one of them divides the other one. More formally, if A_i divides A_i+1 or A_i+1 divides A_i, then these are happy elements. All elements of the array should be integers in range [1, M].

Find out the number of traditional arrays of given length N. As the output can be very large, find answer modulo 10⁹+7.

Input:
First line contains a single integer T, number of testcases.
Each test case has 2 elements N, length of array and M, the range of elements.

Output:
Single line for the answer of each testcase.

Constraints:
1 ≤ T ≤ 10
1 ≤ N,M ≤ 1000