有一个长度为 n 的序列，特征为 m，满足 a[i]=a[i-m] \ (i>m), a[i]=i \ (i \leq m)。

即 1,2,...,m[i]-1 ,m[i],1,2,...,m[i]-1,m[i],...(n-i) \ mod \ (m[i]+1) 。

例如 n=7,m=3 时，序列如下：

1 ,2, 3, 1, 2, 3, 1

现可删除若干元素（也可以不删，也可以全删），问会出现多少不同的序列？ 序列不同当且仅当长度不一致或者某一位不同。

答案对 10^9+7 取模，即 ans \ \% \ 1000000007。

第一行输入一个 T \ (1 \leq T \leq 1000)，表示 T 组数据。

输入两个整数 n,m \ (1 \leq m,n \leq 2 \times 10^5)

保证输入的 n 的总和不超过 2 \times 10^5。

输出会出现多少不同的序列。