求满足以下条件序列$a[1 \ldots k]$个数：

1. $a[i] \in [1,n]$

2. $a[i]$单调不减

3. 所有$a[i]$最大公约数为$1$

答案对$10^9+7$取模。

输入格式

第一行一个整数$T$表示数据组数

接下来$T$行，每行两个整数$n,k$

输出格式

输出$T$行

样例一

input

5
2 4
3 4
5 2
1 10
9812 16

output

4
13
10
1
694387123

限制与约定

$T \le 5$

对于20%的数据，$n \le 100$。

对于70%的数据，$n \le 10^7$。

对于100%的数据，$n \le 10^9,k \le 1000$

时间限制：1s

空间限制：512MB