暂无测试数据。

Description

\(\text{Scarral}\) 最近在潜心研究数学，他发现了一类很有趣的数字，叫做无平方因子数。也就是这一类数字不能够被任意一个质数的平方整除，比如 \(6=2\cdot3\)、\(7=7\)、\(10=2\cdot5\) 都是无平方因子数，而 \(12=2^2\cdot3\) 则不是。所以 \(\text{Scarral}\) 在思考一个问题——选择不超过 \(K\) 个 \(N\) 以内的正整数乘起来，使得乘积是一个无平方因子数，有多少种取法？（每个数只能取一次）

Input

第一行一个整数 \(T\) 表示数据组数。
接下来 \(T\) 行，每行两个整数 \(N\)、\(K\)，意思如题面所述。

Output

对于每一组数据，输出一个整数表示取法的方案数对 \(1e9+7\) 取模后的数值。

Sample

Sample input

3
1 1
6 4
4 2

Sample output

1
19
6

Hint

\(10\%\) 的数据：\(N\leq 8\)；
\(40\%\) 的数据：\(N\leq 16\)；
\(70\%\) 的数据：\(N\leq 30\)；
\(100\%\) 的数据：\(1\leq T\leq 5\)；\(1\leq K\leq N\leq 500\)。