我们称一个由正整数组成的数组 $\{a_1, a_2, \dots, a_n\}$ 是“好的”，当且仅当对于每个 $1 \le i < n$，$a_{i+1}$ 都能被 $a_i$ 整除。请注意，我们认为所有长度为 1 的数组都是好的。

给定两个整数 $n$ 和 $m$，请计算长度不超过 $n$ 且最大元素不超过 $m$ 的“好的”数组的数量。由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含两个整数 $n, m$ ($1 \le n, m \le 10^9$)，表示一个测试用例。

保证满足 $\max(n, m) > 10^3$ 的测试用例数量不超过 50，满足 $\max(n, m) > 10^6$ 的测试用例数量不超过 10，满足 $\max(n, m) > 10^8$ 的测试用例数量不超过 1。

输出格式

对于每个测试用例，输出一行，包含答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

5
2 4
3 5
10 12
24 17
114514 1919810

输出 1

12
31
3915
190204
13530870

说明

当 $n = 2, m = 4$ 时，所有好的数组为：

• $\{1\}, \{2\}, \{3\}, \{4\}$
• $\{1, 1\}, \{1, 2\}, \{1, 3\}, \{1, 4\}$
• $\{2, 2\}, \{2, 4\}$
• $\{3, 3\}$
• $\{4, 4\}$