Free from square

Problem Description

There is a set including all positive integers that are not more then $n$. HazelFan wants to choose some integers from this set, satisfying: 1. The number of integers chosen is at least $1$ and at most $k$. 2. The product of integers chosen is 'free from square', which means it is divisible by no square number other than 1. Now please tell him how many ways are there to choose integers, module 10^9+7.

Input

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases. For each test case: A single line contains two positive integers $n,k(1\leq n,k\leq500)$.

Output

For each test case: A single line contains a nonnegative integer, denoting the answer.

Sample Input

2

4 2

6 4

Sample Output

6

19

Source

2017 Multi-University Training Contest - Team 7

https://acm.hdu.edu.cn/showproblem.php?pid=6125